Computational complexity classes and their relations

learn more… | top users | synonyms

9
votes
0answers
37 views

Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?

I was reading a paper of Buhrman and Homer “Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy”. On the bottom of page 2 they remark that the results of Kannan imply that ...
1
vote
1answer
36 views

Complexity of Determining Linear Separability

Be $X := \{x_1,...,x_N\}$ and $Y := \{y_1,...,y_N\}$ subsets of $\mathbb{R}^d$. What is/are the most efficient existing algorithm/s for determining whether X and Y are linearly separable and what is ...
25
votes
1answer
400 views

Examples where the uniqueness of the solution makes it easier to find

The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. ...
1
vote
2answers
193 views

For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?

The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows: Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Does there exist ...
8
votes
0answers
178 views

How powerful is exact “quantum” computing if you suspend unitarity?

Short Question. What is the computational power of "quantum" circuits, if we allow non-unitary (but still invertible) gates, and require the output to give the correct answer with certainty? This ...
0
votes
0answers
37 views

Can there exist a single Turing machine complete for PTIME, or for $\#P_1$?

In "The Complexity of Enumeration and Reliability Problems", Valiant mentions the existence of a single Turing machine that is complete for the class $\#P_1$ (i.e., $\#P$ with unary input). On page ...
0
votes
1answer
68 views

PAC algorithms for APX-Hard problems

Do there exist polynomial time algorithms that admit Probably Approximately Correct (PAC) bounds for APX-Hard problems? That is, does there exist a problem $P$ that is APX-Hard, such that for every ...
2
votes
1answer
102 views

Parallel (NC) replacements for Gaussian elimination?

Suppose one has an matrix $A$ with $c$ columns and $r$ rows with entries in the binary field $GF(2)$. One wants to determine its rank, and a basis for its null-space. These can be computed ...
11
votes
1answer
237 views

$\mathsf{NP} \cap \mathsf{coNP}$ as oracle

Does $\mathsf{NP^{NP \,\cap\, coNP}=NP}$ hold? Clearly $\mathsf{NP^{NP}\neq NP}$, but it seems to me that $\mathsf{NP\cap coNP}$ is "deterministic" which makes me believe this is true. Is there a ...
15
votes
2answers
329 views

A good reference for complexity class operators?

I'm interested if there exist any good expository articles or surveys to which I can refer when I write about complexity class operators: operators which transform complexity classes by doing things ...
0
votes
0answers
119 views

Intermediate problems between nonuniform $NL$, $Mod_n L$ and $P$?

A related question asked about intermediate problems between $L$ and $NL$. I'm interested in problems between the nonuniform versions of $NL$, $Mod_n L$ and $P$. This makes sense as it is known that ...
2
votes
0answers
163 views

Does $P\neq NP$ imply any larger separation?

I've asked a similar question in cs.se, but didn't get a satisfying answer. Assuming $P\neq NP$, what can we say about the runtime of any algorithm for an $NP$-complete problem? Obviously, it means ...
11
votes
2answers
304 views

Is NP in $DTIME(n^{poly\log n})$?

Is NP in $DTIME(n^{poly\log n})$?
2
votes
2answers
125 views

Set packing with maximum coverage objective

We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$. Set-Packing asks how many disjoint sets we can pack, and is defined ...
0
votes
0answers
64 views

What kind of computations or algorithms give rise to iterated logarithm and inverse Ackermann function?

I heard a statement saying that iterated logarithm and inverse Ackermann function are usually the slowest growing functions used in computer program complexity analysis. Is that true? What kind of ...
1
vote
1answer
119 views

Figuring EasyVer problems - problems whose witness can be verified in time independent on the instance size

In a related question I've defined a class of graph problems which are verifiable using a time related only on the size of the witness: $EasyVer=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness ...
7
votes
0answers
128 views

What relations are there between a problem hardness and the hardness of verifying a witness?

I had some hard times trying to formulate the question, so I'll start with some examples: Suppose you are given a Dominating Set instance, $<G,k>$. Now suppose I give you a set of vertices $D$ ...
7
votes
0answers
123 views

Is the following “Occam's razor” decision problem a member of P?

While thinking about natural language processing, I came up with the following NP problem: OCCAM-k: Given a fixed natural number $k$, consider the following input: a natural number of states $S$ in ...
14
votes
1answer
244 views

Natural candidate against the Isomorphism Conjecture?

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic (p-isomorphic) to each other. The key significance of the conjecture is ...
6
votes
1answer
138 views

Coding theory and complete problems

Coding theory is an useful topic in theoretical computer science. There are known examples of problems coming from coding theory which turn out to be NP complete. My questions are the following: ...
15
votes
3answers
298 views

Complexity class separations without hierarchy theorems

Hierarchy theorems are fundamental tools. A good number of them was collected in an earlier question (see What hierarchies and/or hierarchy theorems do you know?). Some complexity class separations ...
5
votes
3answers
355 views

What would be the consequences of PH=PSPACE?

A recent question (see Consequences of NP=PSPACE) asked for the "nasty" consequences of $NP=PSPACE$. The answers list quite a few collapse consequences, including $NP=coNP$ and others, providing ...
0
votes
1answer
93 views

Problems of similar complexity for different measures

It is a common belief that $\mathbf{P}\subsetneq\mathbf{PSPACE}$, thus (most likely) there are problems that are "harder" for time than for space. But is there a problem in $\mathbf{P}$ with a ...
21
votes
3answers
591 views

Optimization problems with good characterization, but no polynomial-time algorithm

Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the ...
20
votes
4answers
1k views

Consequences of NP=PSPACE

What would be the nasty consequences of NP=PSPACE? I am surprised I did not found anything on this, given that these classes are among the most famous ones. In particular, would it have any ...
7
votes
1answer
132 views

Natural problem arising from diagonalization?

Diagonalization is a frequently used technique in complexity theory. However, the problems (sets) that are created by diagonalization rarely correspond to anything natural. It would be interesting to ...
5
votes
0answers
217 views

Why do we believe $\mathsf{fewP \ne NP}$?

$\mathsf{fewP}$ ($\mathsf{NP}$ with few witnesses, see the zoo) is one of the important ambiguity-bounded sub-classes of $\mathsf{NP}$. There are interesting natural problems in this class that are ...
13
votes
3answers
300 views

Can limit of hard languages be easy?

Can the following all hold simultaneously? $L_s$ is contained in $L_{s+1}$ for all positive integers $s$. $L = \bigcup_s L_s$ is the language of all finite words over $\{0,1\}$. There is some ...
1
vote
1answer
156 views

Would polynomial solution for #P-complete problem mean polynomial solution for PSPACE problem?

After looking at textbooks and trying to derive by my own deductive abilities, I was not able to see whether polynomial solution for #P-complete problem (that is counting problem done in polynomial ...
2
votes
0answers
75 views

Are NQP and QMA comparable?

Both definitions try to create a quantum analog for NP. NQP's definition comes from non-deterministic algorithms: it contains languages for which a Quantum Algorithm accepts with non-zero probability ...
16
votes
1answer
350 views

What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?

Following Josh Grochow's suggestion, I am converting my comment from a previous question into a new question. What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$? Here $\mathsf{UP}$ is ...
6
votes
1answer
222 views

Separating $DSPACE(f)$ and $DTIME(2^f)$: is there any function computable in time $2^{O(f)}$ but not in space $O(f)$?

For $f(n)\ge n$, $$\mathsf{DSPACE}(f(n)) \subseteq \mathsf{DTIME}(2^{O(f(n))}).$$ Is there any function $f$ for which this containment is known to be proper?
3
votes
0answers
100 views

Computing the permanent with polylog size matrices

The complexity of computing the permanent of a $l\times l$ binary matrix is known to be $\#\mathsf{P}$-complete, from the famous result of Valiant, where $l = \Theta(n)$. We know that the problem is ...
7
votes
1answer
192 views

Reference for Turing to many-one reductions

I am looking for a reference on `reducing' Turing reductions to many-one reductions. I have in mind a statement of the following form (similar enough statements would also satisfy me): Theorem. If ...
3
votes
1answer
121 views

What is the descriptive complexity of the basic modal logic?

This is kind of multiple questions in one. Let's consider $\phi$ a formula in the basic modal language (that is, in propositional language based on a set of propositional variables $\Phi$, plus one of ...
2
votes
1answer
316 views

On $NP=coNP$ problem in average case

$1)$Can a $NP$-hard problem can have short certificates that can be verified in deterministic polynomial time for ALL but $\frac{1}{n}$ of the NO instances$? $2)$ Can one concoct versions of NP ...
11
votes
2answers
485 views

In what class are randomized algorithms that err with exactly 25% chance?

Suppose I consider the following variant of BPP, which let us call E(xact)BPP: A language is in EBPP if there is a polynomial time randomized TG that accepts every word of the language with exactly ...
4
votes
1answer
142 views

Arithmetic Analogues of P versus BPP

In the arithmetic hierarchy, is there an analog of $P$ versus $BPP$? Particularly is there a notion of randomness there? If there is no such analogy, why is randomness in the resource bounded case ...
4
votes
0answers
139 views

Physical Proof for P versus BPP

Lipton asks for a physical proof of $P\neq NP$. Can we even ask for a physical proof for understanding $P=BPP$ or $P\neq BPP$? Is there anything in physics that lets us avoid randomness? ...
6
votes
2answers
194 views

Proof Strategies on P versus BPP

Typically to show $P=NP$, one has to show an NP complete problem has a polynomial time solution and to show $P\neq NP$, has to show an NP complete problem has superpolynomial lower bound. These are ...
7
votes
1answer
335 views

Is there a problem in ZPP not yet in P?

Primality was a nice problem that was in ZPP but was not known to be in P. Is there a (preferably simple to state) problem of which we can prove that it is in ZPP but we do not know whether it is in P ...
6
votes
1answer
181 views

Consequences and state-of-the-art of NP ≠ ZPP?

Consider the complexity classes $\mathsf{NP}$ and $\mathsf{ZPP}$. Whether the two classes are equal is an open question, but as far as I know, $\mathsf{NP} = \mathsf{ZPP}$ is not known to imply ...
7
votes
1answer
246 views

Transform a CNF into an equivalent 3-CNF defined on the same variables

(I posted this question on CS ten days ago, with no answer since then - so I post it here.) Any CNF formula can be transform in polynomial time into a 3-CNF formula by using new variables. It is not ...
10
votes
2answers
292 views

Intuition for the UP class

UP class is defined as such: The class of decision problems solvable by an NP machine such that If the answer is 'yes,' exactly one computation path accepts. If the answer is 'no,' all ...
11
votes
0answers
262 views

Does ${\bf L} \neq {\bf NL}$ imply ${\bf P} \neq {\bf NP}$?

This question is inspired by this question Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$? We do know that ${\bf L}$ could equal ${\bf NL}$ and at the same time ${\bf P}$ ...
7
votes
1answer
220 views

Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?

If we can prove that $\mathsf{L}=\mathsf{P}$, does it imply that $\mathsf{NL}=\mathsf{NP}$ ? I thought it is the case, but I cannot prove it (also for the converse).
9
votes
2answers
183 views

Exact complexity of a problem in $\cap_{m \geq 2}\mathsf{AC}^0[m]$

Let $x_i \in \{-1,0,+1\}$ for $i \in \{1,\ldots,n\}$, with the promise that $x = \sum_{i=1}^n{x_i} \in \{0,1\}$ (where the sum is over $\mathbb{Z}$). Then what is the complexity of determining if $x = ...
0
votes
0answers
148 views

Technical clarification on Promise problems

$xSAT$ is a problem in $NP\cap coNP$ defined by Even, Selman and Yacobi in http://www.sciencedirect.com/science/article/pii/S001999588480056X. Consider $\Pi$ to be the problem to decide if there is ...
8
votes
1answer
268 views

What is wrong with this $\mathsf{L} \subseteq \mathsf{L}-$uniform $\mathsf{NC}^1$ argument?

The following is not believed to be true: $\mathsf{L} \subseteq \mathsf{L}-\mbox{uniform } \mathsf{NC}^1$ Can you help me see where the argument breaks down? The directed reachability problem ...
14
votes
0answers
155 views

Do circuits allow to derive EXPSPACE hardness results?

It seems that encoding an NP-complete problem succinctly often makes it nexptime-complete. For instance, 3SAT or HAMILTONIAN PATH become NEXPTIME-complete when the encoding is succint, eg using ...