Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
400
questions
0
votes
1answer
25 views
P vs NP characterization confusion
I know that $P \subseteq NP$, but for a problem in $P$, e.g. MST in a graph, is it a correct statement to say that:
The MST problem belongs in NP-Class.
(I mean, i think it is correct, but could ...
2
votes
1answer
46 views
Is there any consequence to the existence of $\mathsf{PSPACE}$-complete sparse language like with Mahaney's theorem?
Mahaney's theorem states that the existence of $\mathsf{NP}$-complete sparse language would lead to $\mathsf{P = NP}$. Is there any result result regarding the same for the complexity class $\mathsf{...
-1
votes
3answers
163 views
Why don't passwords prove P != NP?
Pardon my ignorance on the matter but,
Verifying passwords = Polynomial (linear)
Guessing passwords = Exponential
Since each guess has nothing to do with one another, exponential time is best possible ...
1
vote
2answers
45 views
What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$
Is it known if complexity class of all sparse languages is contained within e.g. $\mathsf{EXP}$ or $\mathsf{EXPSPACE}$? Or what is the smallest time or space complexity class that contains complexity ...
4
votes
1answer
362 views
Are there any known W[3] or W[3]-hard problems?
We are currently working on a variant of domination parameter and we have shown that it is in W[3] with regard to parameterized complexity. To show it is W[3]-complete, we must show the problem is W[3]...
1
vote
0answers
17 views
Is QMA known to contain Co-NP?
Is QMA known to contain Co-NP?
If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
5
votes
1answer
84 views
Conway's Game of Life: Is it really P-complete?
Wikipedia claims that the Game of Life is P-complete (or the decision problem version of it is; the function version, I suppose, would then be FP-complete).
Colloquially, P-complete and FP-complete ...
1
vote
1answer
45 views
Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP
In this paper (https://arxiv.org/pdf/1706.06708.pdf) the authors prove that optimally solving the $n\times n\times n$ Rubik's Cube is an NP-complete problem. In the process, they must show that the ...
0
votes
1answer
40 views
If X is polynomial-time reducible to Y and X is polynomial-time reducible to Z then Y is polynomial-time reducible to Z?
If $X$ is polynomial-time reducible to $Y$ and $X$ is polynomial-time reducible to $Z$,
$Y$ is polynomial-time reducible to $Z$?
If $X \leq_p Y$ and $X \leq_p Z$ then $Y \leq_p Z$?
True, false or we ...
-1
votes
1answer
34 views
If X is in NP then $\overline{X}$ is in NP. True, false or “we don't know”? Why?
If X is in NP then $\overline{X}$ is in NP.
True, false or "we don't know"? Why?
-3
votes
1answer
38 views
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
Is this true, false or "we don't know"? Why?
2
votes
0answers
44 views
Complexity of approximating a function value using queries
I am looking for information on problems of the following kind.
There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You ...
0
votes
1answer
21 views
Complexity of generating power sets
Suppose I have two sets $A$ and $B$ containing integers. Let $B'$ be the power set of $B$. Then suppose I have an algorithm that enumerates all possible pairings of elements in $A$ and $B'$ to apply a ...
1
vote
1answer
26 views
A question regarding definition of Deterministic Subexponential Time (SUBEXP)
First Look at the definition of SUBEXP from Complexity Zoo:
SUBEXP: (Deterministic Subexponential-Time)
The intersection of DTIME($2^{n^\epsilon}$) over all $\epsilon$>0. (Note that the algorithm ...
1
vote
1answer
34 views
Arthur-Merlin protocol
I recently learned about the Arthur-Merlin protocol, and we defined the complexity classes $AM,MA$.
We have also seen that there exists a theorem stating that $AMAMAM...AM=AM$, however we have not ...
0
votes
1answer
51 views
Is finding solution to a system of 2SAT equations seperated by OR (DNF form) in NP
I want to know if finding solution to a specific number of 2SAT equations sepearted by OR gate (DNF form as below) is in P or NP.
The equation has total n variables and each clause is a 2SAT equation ...
0
votes
1answer
24 views
If $PSPACE^{SAT}=PSPACE$ and $PSPACE \subseteq EXP$, then why does $EXP^{SAT}$ not necessarily equal to $EXP$?
I read the following claim:
$PSPACE^{SAT}=PSPACE$
$EXP^{SAT}$ is not necessarily the same as $EXP$
The first claim makes sense; $PSPACE \subseteq PSPACE^{SAT}$ trivially, and for any language $B \in ...
1
vote
1answer
30 views
why is $\Pi_2$ smaller than $NP\cap coNP$
Consider the language $A=\{(\phi_1, \phi_2) | \phi_1 \in SAT, \phi_2\in \overline{SAT} \}$. What is the smallest class that $A$ is known to belong to?
Apparently, the answer is $\Pi_2$, although I ...
0
votes
0answers
19 views
If $NTime(2^n) \subseteq DTime(n^n) $, then what can you conclude about $DSpace(n^n)$?
Assume $NTime(2^n)\subseteq DTime(n^n)$, what can you conclude about $DSpace(n^n)$?
I don't know if this is the correct approach, but here was my attempt at an answer:
Let $A \in DSpace(n^n) $ and ...
1
vote
1answer
33 views
Complexity of class finding selection of entries in matrix
Suppose I have a matrix with entries either $x$ or $y$, where the number of rows = number of columns = $n$. If I want to select/circle $n$ entries such that for each row, only exactly one is circled, ...
0
votes
0answers
14 views
Can you give an example of a problem in $EXP^{RE}$ but not In $P^{RE}$
Can you give an example of a problem in $EXP^{RE}$ but not In $P^{RE}$?
0
votes
1answer
30 views
Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$
I'm having a small issue with wikipedia's proof that $RP \subseteq NP$:
An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic ...
1
vote
0answers
17 views
Are there any “natural problems” which are known to be NPI under weak assumptions
Are there any "natural problems" which are known to be NPI under weak assumptions.
By weak assumptions I mean something like $P \neq NP$ or $NP \neq Co-NP$
0
votes
0answers
9 views
What is $S2-EXP•P^{NP}$?
What is $S2-EXP•P^{NP}$?
I saw in on the complexity zoo site without any explanation of what it is.
Coul someone please explain it?
1
vote
1answer
44 views
Proof that if P=PSPACE, RP=BPP
Like the title says. I can't figure out how to prove this.
I think it probably has to do with the polynomial hierarchy collapsing but I'm not sure.
0
votes
1answer
28 views
Is the BPP class closed for union and intersection?
Just like the title says. I want to prove that given two languages $L_1,L_2 \in BPP$, $L_1 \cup L_2 \in BPP$ and $L_1 \cap L_2 \in BPP$
1
vote
1answer
47 views
What is and amplification factor in pseudo-random generators?
I can't seem to find an answer to this. For instance, I have this question:
Show that, if $P=NP$, there aren't any pseudo-random generators (even with amplification factor $n+1$).
My gut tells me this ...
0
votes
0answers
18 views
Is this Correct, the existence of cryptography requires $UP \cap Co-UP \not\subseteq BPP$
Is this Correct, the existence of cryptography requires $UP \cap Co-UP \not\subseteq BPP$?
Or does it require $UP \not\subseteq BPP$?
0
votes
0answers
41 views
What complexity class results would be implied by a proof of the existence of one way functions
What complexity class results would be implied by a proof of the existence of one way functions. (Apart from the obvious $P \neq NP$)
I thik it would imply $P \neq UP$, but what else?
0
votes
1answer
68 views
What complexity class is the TSP problem?
Is the travelling salesman problem (TSP) $FNP$-complete or is it $FP^{NP}$-complete?
1
vote
0answers
25 views
Is $NC_1$ vs PP still an open problem?
Is $NC_1$ vs PP still an open problem?
I done a few searched but I can't find an answer.
0
votes
0answers
21 views
Assuming the Exponential Time Hypothesis is true, what's the fastest possible algorithm that can be produced for NP-complete problems? [duplicate]
Assuming the Exponential time hypothesis is true, what's the fast possible algorithm that can be produced for NP-complete problems?
If 3-Sat takes exponential time, then could it be possible that ...
0
votes
0answers
19 views
What decision problems are their that are outside of elementary but still decidable
What decision problems are their that are outside of ELEMENTARY but still decidable?
I'm curious about problems that are still solveable, but take a very long time to do so.
0
votes
1answer
42 views
What's the complexity class of determing the halting problem of a finite memory Turing machine?
What's the complexity class of determining the halting problem of a finite memory Turing machine?
What is the computational complexity class of determining whether a machine halts on any input if it ...
2
votes
1answer
112 views
Is P/poly known to be in RE?
Is P/poly known to be in RE?
If yes what other classes is it known to be part of.
0
votes
0answers
26 views
What's the class of problems solvable in polynomial time with an exponential number of processors?
What's the class of problems solvable in polynomial time with an exponential number of processors?
I am asking this because I'm curious about the class of problems that could feasable be solved on a ...
0
votes
0answers
20 views
What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat?
What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat?
Would this result in their being a quasi polynomial-time algorithm for all NP-complete problems?
0
votes
1answer
31 views
What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to
What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to?
I suspect that their, NEXP, ESPACE and 2EXPtime respecitvely.
And what bout $NP^{EXP}$
2
votes
0answers
31 views
Are there problems that are known to be in ZPP but not in p
Are there any problems that are known to be in ZPP but not in p?
1
vote
0answers
78 views
What are some of the most ridiculous claims in computer science that we haven't disproved?
What are some of the most ridiculous possible claims in computer science that we haven't disproved?
E.g. For example the claim that ZPP=exptime is absurd but has not been disproven.
-1
votes
1answer
72 views
Close To Cook Reduction given NP != coNP
I am struggling to answer these two questions:
Prove or wrong:
Both are given the assumption that NP != coNP.
For any 2 decision problems S, S', if there is a Cook reduction from S' to S then there ...
1
vote
1answer
86 views
Is every linear language in NL?
I wonder if all the linear languages are in NL?
I was thinking that we can take an input-language $L$ and convert it to linear normal form. If this is not possible, the machine rejects. If the ...
3
votes
0answers
61 views
What about problems that are fixed parameter tractable with an algorithm that does not inspect the parameter?
A parameterized problem is a subset $L \subseteq \Sigma^* \times \mathbb N$, where $\Sigma$ is a finite alphabet. A parameterized problem is fixed parameter tractable, if it could be decided in time $...
0
votes
1answer
33 views
$\text{DSPACE}(O(1))=\text{REG}$ Proof?
I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
2
votes
2answers
64 views
Logarithmic space verifier with unbounded witness
this is a HW question, but its considered a bonus question so I'd appreciate a direction.
Definitions:
The actual question:
**Images taken from HW in TAU Complexity course by Amnon Ta-Shma.
My ...
0
votes
2answers
67 views
How do I prove that $3x^3 +2x + 1 $ is $\omega(x \cdot \log x) $
I am trying to answer this question:
$3x^3 +2x + 1$ is $ \omega(x \cdot \log x)$
My question is how to solve this question.
Here is what I have tried so far:
I applied the definition $3x^3 + 2x + 1 ...
2
votes
1answer
50 views
Complexity classes closed under finite union and intersection, why not infinite union and intersection?
All "nice" Complexity classes are closed under finite union and intersection. (By "nice" I mean ones with complete problems or leaf languages, e.g. P, NP, PSPACE, etc.)
But such classes are not ...
8
votes
1answer
1k views
Can any problem in P be converted to any other problem in P in polynomial time?
Is it possible to convert any problem in P to any other problem in P in polynomial time?
1
vote
1answer
44 views
What complexity class is this set of grammars?
Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, ...
3
votes
1answer
29 views
How to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages
I think this is a basic topic in complexity, but I would like to ask how to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages. From the definition of my textbook, $$co-\mathcal{L}...
