Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
434
questions
0
votes
0answers
26 views
FO-Logic: Two theories in the same complexity class can always be reduced to each other in polynomial space and time
I am currently studying CS and came across a question in my lecture.
Question: Two theories in the same complexity class can always be reduced to each other in polynomial space and time. This is part ...
0
votes
1answer
20 views
Understanding P, NP with an example decision problem
I was reading the definitions of p vs np in [this post] (What is the definition of P, NP, NP-complete and NP-hard?) and I was wondering about how to classify the example decision problem where you ...
2
votes
0answers
30 views
Is there a link between the "padding argument" and the "padding lemma"?
In computability theory here is what the padding lemma says :
Every partial recursive function $\phi_x$ has $\beth_0$ indices and for each $x$ we can find effectively an infinite set $C_x$ of indices ...
3
votes
1answer
71 views
Is Max 3-SAT W[1]-hard?
Is Max 3-SAT a W[1] hard problem, parmeterized by some parmeterize?
I can't find the relevant literature.
I accept any parameterization.
1
vote
1answer
35 views
CVAL is in P (technical detail)
I would like to clarify to myself the way that an algorithm that proves the statement in the title works:
I think the idea should be like this:
We assign the input values to the bit nodes
We ...
0
votes
0answers
17 views
Complexity class of computation of Homfly polynomial
It is claimed that "the problem of the computation of the homfly polynomial is NP-hard." but is it known if it is NP-complete? By the definition of NP-completeness, wouldn't it be enough to ...
3
votes
1answer
82 views
How hard is random SAT?
There is plenty of research into the so-called "random SAT" problem, where we basically try to solve SAT instances with clauses chosen "at random" in some sense.
There are all ...
1
vote
1answer
23 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
72 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
29 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
45 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
52 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
21 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
52 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
59 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
15 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
34 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
33 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
118 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
81 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
36 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
34 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
27 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
142 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
60 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
23 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
49 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
67 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
45 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
53 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
18 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
41 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
53 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
20 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
40 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
126 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
49 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
54 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}\...
1
vote
0answers
138 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
822 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
34 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
29 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
80 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
311 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
63 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
392 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]...
