Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
425
questions
2
votes
1answer
70 views
Polynomial time optimization problems belong to which complexity class?
I know that $\mathsf{P}$ class is only defined for decision problems. Therefore, a problem like "Does there exist an $(s,t)$ path of length $k$ in the graph $G$?" is in $\mathsf{P}$. One can ...
3
votes
1answer
62 views
How to prove that existence of one-way functions implies P≠NP?
Wikipedia:
The existence of such one-way functions... would prove that the complexity classes P and NP are not equal.
How is this proved?
1
vote
0answers
27 views
Consequence of NP-complete, and DP-complete w.r.t. randomized reductions
If a problem is NP-complete with respect to randomized (polynomial time) reductions, but not with respect to deterministic reductions, then we have P $\neq$ BPP (See Question 2 here and its answer).
...
0
votes
1answer
13 views
Different definitions of complexity class DP
I would like to know how different defintions of class DP (also written $D^p$) are equivalent (brief explanations would do). The following are the two definitions I see:
Difference between two NP ...
0
votes
1answer
23 views
Are problems that are fractions of constraints of NP-complete problems also NP-complete?
We know that Hamiltonian path, clique and independent sets are NP-complete but what about half or the square root of each problem or a fraction of $n$ ? That is, for a graph, $G$ of $n$ nodes,
is ...
2
votes
1answer
77 views
How does strong NP-completeness agree with encoding complexity?
I've recently read about the concepts of weak and strong NP-completeness, but faced a problem in wrapping my head around them. I've understood that problems which have numerical parameters (like ...
-2
votes
1answer
47 views
What is the relation between $USAT$, $UP$ and $NP=RP$?
Definition:
AtmostONESAT: SAT instance having promise of $\leq1$ witness.
What is the complexity consequence if an instance of $SAT\in$ AtmostONESAT can be decided whether or not there is a witness in ...
0
votes
0answers
20 views
Polynomial reduction, #P-hard problems, and approximations
Consider two statements.
Statement 1: The problem #3SAT (finding the number of satisfying instances to a 3SAT problem) is #P-hard.
Statement 2: Additively approximating #3SAT upto $\pm 2^{n/2}$ error ...
1
vote
1answer
39 views
Randomized Version of NP
I came across interactive proofs and randomized computation, in particular, i read about the complexity classes $\text{IP}, \text{BPP}, \text{RP}$, etc.
Since the above classes are well-known, I will ...
0
votes
1answer
57 views
$coNP$ and $\oplus P$?
Let a non-deterministic machine have at most $2^{t+1}-1$ accepting paths (highest significant bit position is $t$ and lowest significant bit position is $1$).
I want to decide if the number of ...
1
vote
1answer
34 views
What is the “formula” for “any chipher can be deciphered by a quantum computer”?
There are several quantum complexity classes in different ways analogous to NP: NQP, QMA, and, as I understand, others.
P=NP BPP=NP in simple words means "any cipher can be deciphered by a ...
0
votes
0answers
20 views
Does having a similar constraint while reducing a problem to similar problem to prove np hard means they are same?
I have been trying to find the computational complexity of my optimization problem and found that it is Np-Hard. To prove it to Np-Hard, I try reducing it Nurse Scheduling Problem. I am quite confused ...
1
vote
1answer
13 views
What is the complexity class of finding vertex cover number of a simple graph?
Suppose we have a simple graph $G$. We know that finding the minimum vertex covering set for $G$ is in the NP-hard class. But, what about the complexity class of finding the size of the set, i.e., the ...
1
vote
1answer
10 views
Is it possible to compute the minimum vertex covering set in quasi-polynomial time, by knowing the vertex cover number?
If we know the vertex cover number for a simple graph $G$ denoted by $\tau(G)$, is it possible to find the minimum vertex cover set for $G$ in quasi-polynomial time? As I found, we cannot find any ...
0
votes
0answers
26 views
On classes $\mathsf{\oplus PSPACE}$ and $\mathsf{\oplus L}$?
Savitch's theorem provides $\mathsf{PSPACE}=\mathsf{NPSPACE}$.
Is there a class $\mathsf{\oplus PSPACE}$ analogous to $\mathsf{\oplus L}$ and is it known to be equal to $\mathsf{PSPACE}$?
If $\...
1
vote
0answers
33 views
An opposite method of padding argument on N/DTIME complexity class
Is there a method to prove things with longer input in complexity theory?
For example, using padding argument it's trivial to show that
$\text{NTIME}(n^2) \subseteq \text{DTIME}(n^4) \Rightarrow \...
3
votes
0answers
46 views
Sufficient condition for a complexity class's closure under NP-reductions?
Let us say that there exists a $\mathsf{NP}$-reduction from a problem $A$ to another problem $B$ when there exists a non-deterministic, polynomial-time Turing machine $T$ such that for each $a \in A$, ...
0
votes
1answer
18 views
Is $E^{quasiP}$ equal $E$ or larger?
Let $quasiP$ be the quasipolynomial time complexity class.
Is $E^{quasiP}=E$ false?
Is $E^{DTIME(2^{(\log n)^k})}=E$ false at every $k>1$?
2
votes
0answers
35 views
Language in PSPACE that isn't PSPACE-hard and isn't in PH
Can there exist a language L in PSPACE such that L isn't PSPACE-hard and L isn't in the polynomial hierarchy (PH)? Intuitively, it seems like the answer is no, since TQBF is PSPACE-complete, and any ...
2
votes
1answer
116 views
What is the definition of Infinitely Often class in complexity
I was reading a paper and I came across the term $L\notin i.o.Dtime(2^{n^c}/n^c)$. What is the meaning of this?
0
votes
0answers
12 views
Naming of Monte Carlo and Las Vegas Complexity classes
For Curiosity Sake, I was wondering if there was some history behind the naming of "Las Vegas" and "Monte Carlo" classes.
I've searched on the internet for quite some time now but ...
0
votes
1answer
40 views
What is the computational class of a pushdown automaton with real values?
Say there is a push-down automata, in this example I'll use a deadfish-like set:
+: increase x by 1
0: set x to 0
...
0
votes
2answers
46 views
Prove that $ln(n)^r \in o(n^p)$ for $p>0$ and $r\in \mathbb{R}$
I am trying to proof $f\in o(g)$
Let be $r,p\in \mathbb{R}$ with $p>0$
We have $f(n)=ln^r (n)$ and $g(n)=n^p$
I have already proofed that $ln(n)\in o(n)$ via l'Hospital
$\lim\limits_{n\to \infty}\...
0
votes
0answers
31 views
Complexity class of problem whose running time features binomial coefficient
I've built an algorithm that, starting from an array of $n$ cells and an integer value $s$, builds $\binom{n+s-1}{s}$ vectors (that is, all the ways to add a certain $s$ quantity fully distributed ...
1
vote
0answers
123 views
What is the smallest time/space complexity class for which no sparse language is hard?
For example, whether there exists $\mathsf{PSPACE}$-hard sparse language an open problem, as it is not yet known whether polynomial hierarchy collapses.
But is it a solved problem for larger ...
1
vote
1answer
414 views
Why does SAT-UNSAT $\in NP \implies NP = coNP$
I was reading this post about the DP completeness of the problem SAT-UNSAT (both are well defined in this post). The answer added a note at the end that states the class complexity DP differs from NP, ...
0
votes
1answer
32 views
Is it a sufficient condition to be in NP?
Suppose the following situation.
You have a decision problem $D$.
You know that $SAT$ is $NP$-complete.
You know that $D\leq_p SAT$.
Can you conclude that $D\in NP$?
I think it's true because it ...
0
votes
1answer
28 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
58 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
215 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
55 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
369 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
19 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
88 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
101 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
0answers
76 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
vote
2answers
93 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?
-2
votes
1answer
120 views
If X is polynomial reduction to Y and Y is in NP, then X is in NP? [duplicate]
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
48 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
62 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
43 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
74 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
74 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
35 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
41 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
25 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
34 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}$?
1
vote
1answer
104 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
18 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$
