computational complexity theory; complexity classes, such as P, NP, PSPACE, and so on; resource-limited computation; NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models such as automata, circuits; regular languages; ...

learn more… | top users | synonyms (1)

1
vote
1answer
189 views

Redundancy and Structure of computational problems

It is widely believed that some computational problems such as graph isomorphism can not be NP-complete because it does not possess enough structure or redundancy to be computationally hard (NP-hard). ...
1
vote
0answers
89 views

Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?

Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard? Equally interesting would be to learn about such problems with a ...
2
votes
1answer
175 views

Does Quadratic Programming get easier when it's described by a diagonal matrix?

Generally, Quadratic Programming solves the problem $$\text{Given }Q, c, A, b,\text{ choose }x \text{ to maximize } x^TQx + c^Tx \text{ subject to } Ax \le b$$ In this form, Quadratic Programming is ...
2
votes
0answers
162 views

A natural problem on “cartesian union” of set families (hypergraphs). Does anybody know NP-complete problems related to the notion of cartesian product?

I'm curious whether the problem below is NP-complete. I provide two simple definitions and one example at first. Definition 1. Let $\langle {\cal{S}}_i\rangle\substack{i\in I}$ and $\langle ...
2
votes
1answer
109 views

Any result or conjecture of computaional complexity of formal languange with rational generating function?

As we know that context-free language is in P,any result or conjecture of computaional complexity of formal languange with rational generating function?And more,any result or conjecture of ...
4
votes
0answers
345 views

Computational complexity of multiplication in a nilpotent group?

What is the computational complexity of multiplication in a Carnot group ? Background: A Carnot group is a real nilpotent Lie group $N$ whose Lie algebra $Lie(N)$ admits a direct sum decomposition ...
20
votes
0answers
510 views

A combination of two well-known complexity problems

Suppose you are given two graphs $G$ and $H$ and are told that one of the following two situations occurs. Either they are isomorphic, or one of the graphs contains a Hamilton cycle and the other ...
1
vote
0answers
135 views

Randomized alternative to Buchberger's algorithm

Richard Lipton's blog describes a A New Way To Solve Linear Equations by Prasad Raghavendra. Can the ideas in this algorithm be generalized to systems of polynomial equations to provide a randomized ...
0
votes
1answer
234 views

Algorithm for vector space

I have $n$ vectors $e_1 \in (\mathbb Z/2 \mathbb Z)^m,\dots,e_n \in (\mathbb Z/2 \mathbb Z)^m $ and a vector $ v \in (\mathbb Z/2 \mathbb Z)^m $ I need to find the better algorithm which answers ...
3
votes
0answers
111 views

Gaussian Elimination in terms of Group Action

Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to presence ...
2
votes
2answers
997 views

Generation of All Path in a Directed Acyclic Graph

I am working on a very large dataset of a single DAG whose vertices have a low branching factor. I need to generate all possible (simple) paths starting from the source and write them to a file. My ...
12
votes
2answers
375 views

Optimizing the condition number

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg n.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns ...
7
votes
2answers
631 views

Building a Physical Model to Solve Sudoku

Before asking my questions, allow me to begin with a separate example to help clarify what I'm driving at. For terms that are not defined formally, please interpret them as you feel would be most ...
10
votes
1answer
532 views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time. ...
10
votes
1answer
241 views

What is the largest tensor rank on matrix.

A tensor rank of tree dimentional matrix $M[i,j,k], i,j,k\in [1,\ldots,n]$ is a minimal number of vectors $x_i,y_i,z_i$, such that $M=\sum_{i=1}^d x_i\otimes y_i\otimes z_i$. From dimension argument ...
3
votes
2answers
163 views

Determination of rationality and computing a rational parametrization

Suppose I have a hypersurface in $\mathbb{C}P^n$ given by some $f(z_1, \dots, z_{n+1}) = 0.$ Is there an algorithm which returns a rational parametrization if there is one, and "not rational" ...
4
votes
2answers
294 views

Sets of vectors related by a rotation

We have a two sets of vectors ($\mathbb{C}^d$), $A=\{ v_1, \ldots v_n\}$ and $B=\{u_1, \ldots u_n\}$. The question is if there is an efficient solution (polynomial in $n$) for checking whether $A$ ...
16
votes
1answer
2k views

How fast can we *really* multiply matrices?

Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.8})$ for the multiplication of two $n \times n$ matrices. However, the constant is so large that ...
0
votes
1answer
184 views

graph to tree and graph isomorphism problem

Sorry if the following are stupid questions (i do not know much about the graph theory). 1. Motivation we do not know the graph isomorphism problem in class P or NP complete and it is P in the ...
3
votes
1answer
330 views

Complexity of convex polytope volume calculation ? (Volume of Voronoi cell) (Error probability)

Assume I have polytope in R^k given by N (k<< N) linear inequalities (A_i x < b_i). I guess complexity of its volume calculate is higher than linear in "N", am I right ? (Is the complexity ...
13
votes
1answer
561 views

Forcing over set theory versus forcing over arithmetic

I've been trying to understand better some of the research on forcing over bounded arithmetic and its connections with lower bounds in complexity theory. For example, Takeuti and Yasumoto have some ...
2
votes
1answer
263 views

Oracle Results: P^A = NP^A

Context In the work of Baker, Gill, Solovay, we know that there exists some oracle A s.t. $$P^A = NP^A$$. Now, in CCAMA, this oracle $A$ is given as an EXP complete language. Question: Can we do ...
1
vote
0answers
76 views

Deciding / Approximating Parity of Small Depth Decision Trees

Let C be a circuit such that: C: $\{0,1\}^n$ to $\{0,1\}$ the top most gate is a parity gate all the inputs to the parity gate are small depth decision trees there is a total of $2^{ log^k n}$ ...
3
votes
2answers
1k views

Computational complexity of calculating the nth root of a real number

Several sources state that the computational or time complexity of square rooting is the same as that of multiplication (or division). See for example: Jean-Michel Muller, "Elementary Functions: ...
1
vote
3answers
1k views

How to get the largest subset of a set of sets of intervals with no overlapping intervals

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}} Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise. Example: Input ...
2
votes
3answers
270 views

Generating a set of integer passwords that can be securely authenticated

First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it. My question is as follows. Given a positive integer $k$, determine a set of properties ...
4
votes
2answers
231 views

Computational complexity of Knot polynomials

What's known about computational complexity of different types of knot invariant polynomials? For example, Evaluating Jones Polynomial is known to be #P hard. Is there any reference that surveys such ...
5
votes
3answers
551 views

computational complexity of primitive recursive functions

If we have a rewrite system for primitive recursive functions, which simplifies each term according to how the function was defined, then what is the computational complexity of this calculation? That ...
4
votes
2answers
251 views

How small can a language in NP\P be?

How small can a language in $NP$ but not in $P$ be? Of course, I don't expect a proof that there exists a language in $NP\setminus P$, so instead I'll ask: Can we rule out any of these conjectures? ...
17
votes
1answer
2k views

Möbius Randomness of the Rudin-Shapiro Sequence

The Rudin-Shapiro sequence (also known as the Golay-Rudin-Shapiro sequence) is defined as follows. Let $a_n = \sum \epsilon_i\epsilon_{i+1}$ where $\epsilon_1,\epsilon_2,\dots$ are the digits in the ...
13
votes
3answers
475 views

Complexity of equitable partitions

We are talking about undirected simple graphs and partitions of their vertex sets into disjoint non-empty cells. Such a partition is equitable if for any two vertices $v,w$ in the same cell, and any ...
3
votes
1answer
232 views

Diagonalization and classes of computable functions

Fix a standard effective listing $(\phi_e)_{e\in\omega}$ of the partial computable functions from $\omega$ to $\omega$. Let $\mathcal{C}$ be a class of computable total functions $\omega\rightarrow ...
2
votes
2answers
503 views

sparsity of QR decomposition

Hi, everyone! I have a sparse $n \times n$ matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in $A$. Now I use QR factorization to decompose $A$ into an orthogonal matrix $Q$ and ...
3
votes
1answer
221 views

Complexity of Labeled Graph Homomorphism

The following recreational math problem has been floating around work: We're given an $m \times n$ grid ($m,n$ positive integers). We wish to label the elements of the grid with letters so that we ...
2
votes
1answer
121 views

Maximizing positive definite quadratic using the eigendecompoisition

Consider the problem: $\textrm{max}\;\; x^T Q x$ subject to $||x||_\infty \leq 1$, where $Q$ is a positive definite matrix. I believe this problem is NP-hard (although I have only found hardness ...
3
votes
1answer
119 views

Counting connected fundamental domains of actions on Cayley graphs

The following question arises, for me, from mathematical music theory: Write $({\Bbb Z}^n,E_n)$ for the Cayley graph of ${\Bbb Z}^n$ relative to standard free generators. Given a subgroup $L$ of ...
1
vote
1answer
460 views

k-uniform k-partite hypergraph matching in polynomial time

I have what seems like an elementary question, but google didn't throw up any answers for it. I would appreciate any pointers that MO users may provide. It is well known that for $k\geq 3$ finding ...
3
votes
0answers
166 views

Kolmogorov complexity with bounded ressources

Thanks to symetry of information (i.e $\forall x,y, K(xy) = K(x) + K(y|x) - O(log(|x| + |y|)$), one can easily show that : $ \exists N \forall x, (|x| = n^{log(n)} and |x| \geq N), \exists y, (|y| ...
3
votes
1answer
123 views

Quick tests for Self complementary vertex transitive graphs

Are there any quick tests to determine if a graph is Self complementary vertex transitive? That is if the graph is self complementary vertex transitive the answer should be yes.
6
votes
1answer
345 views

Vertex transitive graphs

Does having vertex transitivity make the problem of calculating independence and chromatic numbers easier?
3
votes
2answers
567 views

symmetric difference of languages - both are in NP and coNP

I have this problem, Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like: $L_1 \oplus L_2$ = {x | x is in exactly one of ...
3
votes
0answers
152 views

Best lower bound for proof complexity of graph asymmetry

Graph automorphism problem ( GA) of determining whether a graph has a nontrivial automorphism is a good candidate for a problem in $NP$-intermediate. I'm looking for references that study the ...
0
votes
2answers
104 views

Bounding 2nd Eigenvalue of a Pseudo-Rotation-ish matrix

Let $p,q$ be arbitrary primes. Let $N = p * q$. Let $I$ be the $N * N$ identity matrix. Let $R$ be the $N * N$ matrix defined as follows: $R[x_0 * p + y_0, x_1 * p + y_1]=1$ if and only if $x_0+1 ...
3
votes
2answers
189 views

Form a $\mathbb{Z}^d$ lattice cycle from given lengths

Suppose you are given a list of integer lengths, e.g., $(5,3,2,2,1,1,2,1,1)$. The task is to decide if they can form a closed cycle in $\mathbb{Z}^d$ by connecting segments of those lengths in order, ...
3
votes
2answers
566 views

Computational complexity of unconstrained convex optimisation

What is known about the relationship between unconstrained convex optimisation and computational complexity? For example, for which optimisation problems and which gradient descent algorithms is one ...
14
votes
4answers
3k views

What would be some major consequences of the inconsistency of ZFC?

I was happily surfing the arXiv, when I was jolted by the following paper: Inconsistency of the Zermelo-Fraenkel set theory with the axiom of choice and its effects on the computational complexity by ...
6
votes
1answer
542 views

NP-hardness of a graph partition problem?

I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic? Here $E$ is ...
4
votes
1answer
438 views

Infinite monkeys computing … triangle area?

I wonder if it is possible to specialize the question: (a) What is the probability that a random Turing Machine program will halt?, to: (b) What is the probability that a random Turing Machine ...
10
votes
2answers
457 views

What is the computational-complexity-theoretic analogue of computable inseparability? For example, if P is not NP, are there disjoint NP sets with no separation in P?

Disjoint sets $A$ and $B$ are computably inseparable, if there is no computable separating set, a computable set $C$ containing $A$ and disjoint from $B$. The existence of c.e. computably inseparable ...
12
votes
1answer
536 views

Does every feasible partial order relation on the natural numbers extend to a feasible linear order relation?

It is well known that every partial order on a set can be extended to a linear order on that set. That is, for every partial order $\lhd$ on a set $X$, there is a linear order $\prec$ on $X$ such that ...