Questions tagged [complexity-classes]
Computational complexity classes and their relations
123
questions
41
votes
2
answers
4k
views
Semantic vs. Syntactic Complexity Classes
In his "Computational Complexity" book, Papadimitriou writes:
RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the ...
- 16.5k
37
votes
5
answers
9k
views
NEXP-complete problems
There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one ...
21
votes
2
answers
2k
views
Problem in BPP but not known to be in RP or co-RP
Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?
- 6,970
19
votes
1
answer
690
views
Looking for a nice problem inside SC but not in the first two levels
The complexity zoo doesn't have much about the $\mathsf{SC}$. I am looking for a nice$^\dagger$ problem that is in higher levels of the hierarchy, i.e. a problem in $\mathsf{DTimeSpace}(n^{O(1)},\lg^{...
- 21.5k
55
votes
2
answers
4k
views
Can one amplify P=NP beyond P=PH?
In Descriptive Complexity, Immerman has
Corollary 7.23. The following conditions are equivalent:
1. P = NP.
2. Over finite, ordered structures, FO(LFP) = SO.
This can be thought of as "...
- 18.9k
38
votes
3
answers
4k
views
Does $VP \neq VNP$ imply $P \neq NP$?
As far as I understand, the geometric complexity theory program attempts to separate $VP \neq VNP$ by proving that the permament of a complex-valued matrix is much harder to compute than the ...
- 383
20
votes
1
answer
1k
views
Consequences of UP equals NP
EDIT at 2011/02/08:
After some references finding and reading, I decided to separate the original question into two separate ones. Here's the part concerning UP vs NP, for the syntactic and semantic ...
- 7,638
17
votes
2
answers
2k
views
12
votes
2
answers
2k
views
Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?
By http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf
If $A$ is a PSPACE-complete language, $P^{A}=NP^{A}$.
If $B$ is a deterministic polynomial-time oracle, $P^{B}\ne NP^{B}$ (assuming $P\...
- 709
23
votes
1
answer
1k
views
Do all complexity classes have a leaf language characterization?
Leaf languages are a beautiful way to uniformly define many complexity classes. Most complexity classes are usually specified by a model of computation (e.g., deterministic/randomized TM), and a ...
- 13.5k
63
votes
8
answers
4k
views
What is the complexity class most closely associated with what the human mind can accomplish quickly?
This question is something I've wondered about for a while.
When people describe the P vs. NP problem, they often compare the class NP to creativity. They note that composing a Mozart-quality ...
user1338
38
votes
4
answers
2k
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. ...
- 11.3k
29
votes
2
answers
2k
views
What are the consequences of Parity-L = P?
Parity-L is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or ...
- 8,821
22
votes
3
answers
1k
views
Problems outside of P that are not P-hard
While reading an answer by Peter Shor and an earlier question by Adam Crume I realized that I have some misconceptions about what it means to be $\mathsf{P}$-hard.
A problem is $\mathsf{P}$-hard if ...
- 10.2k
20
votes
1
answer
1k
views
Is there a better than linear lower bound for factoring and discrete log?
Are there any references that provide details about circuit lower bounds for specific hard problems arising in cryptography such as integer factoring, prime/composite discrete logarithm problem and ...
- 2,208
19
votes
1
answer
551
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 ...
- 11.3k
10
votes
3
answers
598
views
Benefits for syntactic and semantic classes
This is a post separated from Consequences of UP equals NP, and also a follow-up question to Semantic vs. Syntactic Complexity Classes.
In the above post we learned about the semantic and syntactic ...
- 7,638
9
votes
2
answers
1k
views
XOR-SAT to Horn-SAT reduction
Horn-SAT (conjunction of Horn clauses) is P-complete and XOR-SAT (conjunction of xor clauses) is in P. This means that there is a reduction from XOR-SAT to Horn-SAT weaker than a polynomial reduction.
...
7
votes
2
answers
839
views
Is there a PSPACE-intermediate language?
Suppose PH is strictly contained in PSPACE. Is there a problem in PSPACE that is not in PH and not PSPACE-complete?
I encountered a language that is in PSPACE. The question is whether it's in PH. So ...
- 551
231
votes
11
answers
121k
views
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct?
Also on topic: where else (on the internet) is its correctness being discussed?
Note: the focus of this question text has ...
- 1,679
49
votes
4
answers
2k
views
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ $\mathsf{polyL}$, where $\mathsf{L}^2 = \mathsf{...
- 2,281
39
votes
7
answers
7k
views
What do we know about provably correct programs?
The ever increasing complexity of computer programs and the increasingly crucial position computers have in our society leaves me wondering why we still don't collectively use programming languages in ...
- 4,670
35
votes
3
answers
1k
views
An Anthology of Complexity Assumptions
In the paper The Random Oracle Hypothesis Is False, the authors (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi) discuss the implications of the random-oracle hypothesis. They argue ...
31
votes
4
answers
5k
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 ...
- 8,598
27
votes
3
answers
1k
views
Succinct Problems in $\mathsf{P}$
The study of Succinct representation of graphs was initiated by Galperin and Wigderson in a paper from 1983, where they prove that for many simple problems like finding a triangle in a graph, the ...
- 1,344
25
votes
4
answers
3k
views
Why do equalities between complexity classes translate upwards and not downwards?
Hey Guys, I understand that the padding trick allows us to translate complexity classes upwards - for example $P=NP \rightarrow EXP=NEXP$. Padding works by "inflating" the input, running the ...
- 1,548
25
votes
3
answers
1k
views
What are the relationships between those hypotheses in Fine-Grained Complexity Theory?
Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" ...
user17918
25
votes
3
answers
2k
views
Hardness of approximation - additive error
There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for ...
- 3,950
24
votes
2
answers
1k
views
What is the big version of NC?
$\mathsf{NC}$ captures the idea of efficiently parallelizable, and one interpretation of it is problems that are solvable in time $O(\log^c n)$ using $O(n^k)$ parallel processors for some constants $c$...
- 10.2k
23
votes
4
answers
1k
views
What are the compelling reasons for believing $L\neq P$?
What are the compelling reasons for believing $L\neq P$? L is the class of log-space algorithms with pointers to the input.
Suppose L=P for the moment. What would a log-space algorithm for a P-...
- 239
22
votes
3
answers
996
views
Limits to Parallel Computing
I am curious in a broad sense about what is known about parallelizing algorithms in P. I found the following wikipedia article about the subject:
http://en.wikipedia.org/wiki/NC_%28complexity%29
The ...
- 221
20
votes
4
answers
1k
views
Parity and $AC^0$
Parity and $AC^0$ are like inseparable twins. Or so it has seemed for the last 30 years. In the light of Ryan's result, there will be renewed interest in the small classes.
Furst Saxe Sipser to Yao ...
- 3,853
18
votes
1
answer
1k
views
Cutting-sticks puzzle
Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2.
Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time?
...
- 1,945
18
votes
1
answer
724
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 the ...
- 18.1k
17
votes
2
answers
2k
views
Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$?
In the "last paragraph" of the "first page" of the following paper:
Vikraman Arvind, Johannes Köbler, Uwe Schöning, Rainer Schuler, "If NP Has Polynomial-Size Circuits, then MA = AM," Theoretical ...
- 16.5k
15
votes
2
answers
1k
views
Quantum analogues of SPACE complexity classes
We often consider complexity classes where we are bounded in the amount of space our Turing machine can use, for example: $\textbf{DSPACE}(f(n))$ or $\textbf{NSPACE}(f(n))$. It seems that early in ...
- 10.2k
14
votes
1
answer
797
views
Is Quasi-polynomial time in PSPACE?
I had done some search on this but I was not able to find an answer either way.
Huck answered it fully. Thanks :)
- 2,589
14
votes
1
answer
640
views
Problems in NC not known to lie in NC2
Are there interesting problems that are in $\mathsf{NC}$ but not known to be in $\mathsf{NC^{2}}$? In the paper 'A Taxonomy of Problems With Fast Parallel Algorithms', Cook mentions that MIS was known ...
- 429
12
votes
1
answer
526
views
Time Hierarchies in DSPACE(O(s(n)))
The time hierarchy theorem states that turing machines can solve more problems if they have (enough) more time.
Does it hold in some way if the space is limited asymptotically?
How does $\textrm{DTISP}...
- 59
12
votes
4
answers
1k
views
Does diagonalization captures the essence of class separation ?
I don't remember having seen a class separation not based on diagonalization and relativization results. Diagonalization could still be used to separate remaining known classes, because non-...
- 1,743
12
votes
2
answers
559
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 ...
- 457
10
votes
1
answer
359
views
A natural problem in $\textrm{S}_2^\textrm{P}$?
The complexity class $\textrm{S}_2^\textrm{P}$ is defined as follows (from Wikipedia):
A language $L$ is in $S_2^P$ if there exists a polynomial-time predicate $P$ such that
If $x \in L$, ...
- 13.5k
10
votes
3
answers
2k
views
Reducing #SAT to #MONOTONE-2SAT
The problem #MONOTONE-2SAT is known to be #P-complete. This means that #SAT can be reduced to it. My question is: given a #SAT instance $F$, which is the transformation that converts $F$ to its ...
- 6,782
8
votes
1
answer
485
views
Are there more polynomial time problems with complexity lower bounds?
I'm looking for more problems in $P$ with classical time complexity lower bounds. Some people might wonder how you could prove such a lower bound. See below.
Exponential Lower Bounds:
Claim: If ...
- 5,127
7
votes
2
answers
2k
views
An analog of DP for the second level of the polynomial hierarchy
The complexity class DP can be defined as the set of all languages that are the intersection of an NP language with a coNP language.
I have a language for which I wish to determine the exact ...
- 221
3
votes
2
answers
951
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 $k$-...
- 9,438
44
votes
3
answers
7k
views
P and NP classes explanation through lambda-calculus
In the introduction and explanation P and NP complexity classes often given through Turing machine.
One of the model of computation is the lambda-calculus.
I understand, that all of models of ...
- 541
37
votes
8
answers
3k
views
Problems with big open complexity gaps
This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves.
To be more ...
- 8,598
36
votes
2
answers
2k
views
Consequences of $SAT \in BQP$
As a TCS amateur, I'm reading some popular, very introductory material on quantum computing. Here are the few elementary bits of information I've learned so far:
Quantum computers are not known to ...
- 6,782
34
votes
3
answers
3k
views
complexity of greatest common divisor (gcd)
Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest ...
- 451