# Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

428 questions
Filter by
Sorted by
Tagged with
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?
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. (...
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 ...
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(...
46 views

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, ...
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$?
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}...
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? ...
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. ...
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 ...
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 ...
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?
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). ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
28 views

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$, ...
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$?
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 ...
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?
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 ...
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 ...
48 views

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 ...
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 ...
380 views

### Are there any known W or W-hard problems?

We are currently working on a variant of domination parameter and we have shown that it is in W with regard to parameterized complexity. To show it is W-complete, we must show the problem is W...
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.)
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 ...
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 ...
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?
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 ...