Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
428
questions
1
vote
1answer
16 views
Consequences of a polytime algorithm for a decision problem reducible to 3SAT
If there is a polynomial time algorithm for a decision problem $A$, which is m-reducible to 3SAT, and 3SAT is NP-complete, does this prove that P=NP?
1
vote
1answer
62 views
Another version of Geography Game
The classic definition of normal “Geography Game” is the following:
Each player on her turn choose a word such that starts with the last letter of the previously choosen word by another player. (...
2
votes
1answer
28 views
Is ${\Sigma_2^\textsf{P}}^\textsf{coNP}\subseteq\textsf{PH}$?
I'd like to know if ${\Sigma_2^\textsf{P}}^\textsf{coNP}\subseteq\textsf{PH}$ or not.
I know ${\Sigma_2^\textsf{P}}^\textsf{NP}=\Sigma_3^\textsf{P}\subseteq\textsf{PH}$, and I wish to know if this ...
0
votes
1answer
43 views
Need help understanding tightest lower bound ( BigOmega ) of n!
I am currently learning complexity theory and wasn't able to find a tightest lower bound to BigOmega(n!), I am quite certain it isn't n^n and so wasn't able to reach to a tightest lower bound, can log(...
1
vote
1answer
46 views
What is the comparator circuit?
The standard circuits $AC^i$, $NC^i$ are constructed using $AND$, $OR$ and $NOT$ of various fan-ins, fan-outs and depths.
What is the comparator gate constituted from?
Structurally why is it believed $...
0
votes
0answers
20 views
What is the depth of comparator circuit required in Gale Shapely and STCONN?
Stable matching problem and $STCONN$ can be solved using comparator circuits (refer https://arxiv.org/abs/1208.2721).
What is the depth of the $CC$ circuit necessary for stable matching? Is it in $CC^...
0
votes
0answers
49 views
A paper claiming that optimization version of symmetric TSP can be solved in polynomial time
In the following paper :
Czopik, J. (2019) An Application of the Hungarian Algorithm to Solve Traveling Salesman Problem. American Journal of Computational Mathematics,9, 61-67.
In the Introduction, ...
1
vote
1answer
58 views
Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
Let $C$ be an uniform complexity class for example $NL$ or $NP$. Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
0
votes
0answers
39 views
Is this combinatorial seach problem NP-complete?
The context: Consider the following optimization problem. Let $f_1,\dots,f_L:\mathbb{R}\to\mathbb{R}$ arbitrary (continous) functions for $L>1$ and $x_k\in\mathbb{R}$ evolve according to
$$
x_{k+1}...
1
vote
0answers
13 views
$W$-hierarchy and parameterized search problems
I have two related questions:
What are the ways to prove that a certain problem is in $W[t]$ in the W-hierarchy for parametrized complexity, except using the straight definition of boolean circuits? ...
4
votes
0answers
32 views
What is a term for a problem that is hard to approximate within a factor $c$?
Let $f$ be a maximization problem. If there is a reduction from SAT to the following problem: "given an integer $c$, decide if there is an $x$ for which $f(x)\geq c$", then $f$ is NP-hard. ...
2
votes
0answers
32 views
Rigorous Definition of a Complexity Class
From Wikipedia, "Complexity classes are sets of related computational problems. They are defined in terms of the computational difficulty of solving the problems contained within them with ...
3
votes
1answer
98 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 ...
4
votes
1answer
71 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
34 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
19 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
26 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
91 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 ...
-1
votes
1answer
53 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
21 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
47 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
65 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
44 views
What is the "formula" for "any cipher 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
20 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
14 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
28 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
35 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
47 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
19 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
38 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
120 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
13 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
46 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
48 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
38 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
126 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 ...
2
votes
1answer
573 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
33 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
64 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
271 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
59 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
380 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]...
2
votes
1answer
84 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
95 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
128 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 ...
1
vote
2answers
100 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
136 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
49 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 ...