Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
9