Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
446
questions
0
votes
0
answers
44
views
Why isn't $P^A = A$?
I have a question regarding oracles.
If I have the complexity class $P^A$ (with $P \subseteq A$), what is it's relationship to the class $A$?
I mean it should be trivial that $A \subseteq P^A$ for all ...
- 109
1
vote
1
answer
27
views
What is different between two classes are 'incomparable' or two classes are 'not equal'?
Arora and Barak states (p. 230) the following:
What is the relation between $BQP$ and $NP$? It seems that quantum computers only offer a quadratic speedup (using Grover’s search) on $NP$-complete ...
- 719
1
vote
2
answers
510
views
What does O( n^{1+o(1)} ) mean
The latest development in solving the max-flow problem promises a ${\displaystyle O(E^{1+o(1)}\log U)}$ solution.
What does it mean, this $O(n^{1+o(1)})$-complexity?
- 27.6k
2
votes
1
answer
121
views
Complexity of the (Complete/Assign) 3-SAT problem?
A complete $k$-CNF formula on $n$ variables $(k\le n)$ is a $k$-CNF formula which contains all clauses of width $k$ or lower it implies.
Let us define the (Complete/Assign) 3-SAT problem: Given $F$, a ...
- 511
1
vote
1
answer
28
views
(Why) is $NP\subseteq coNP/poly$ same as $coNP\subseteq NP/poly$?
If I rememeber right, I read somewhere that $NP\subseteq coNP/poly$ is the same as $coNP\subseteq NP/poly$. Is this true? If yes, is there a relatively simple proof for this?
Definitions
Class $NP/...
- 135
3
votes
1
answer
201
views
Shannon's result that some Boolean functions require exponential circuits
In 1949 Shannon proved, using a non-constructive counting argument, that some boolean functions have exponential circuit complexity, see [1] and many texts on computational complexity. This result has ...
- 8,178
1
vote
0
answers
14
views
Decidablility of complexity properties and its relation to finite description method
We describe formal languages with their finite descriptions. For example we can describe a language simply by set-builder ( $\{ x : \phi(x)\}$) or we can describe something with its corresponding ...
- 358
2
votes
0
answers
22
views
Does this EXPTIME-complete construction work for every DTIME?
I came up with the following after reading the Wikipedia page about EXPTIME, and I am wondering if I am right. I don't think I invented it, I just don't have any textbooks about this subject to find ...
- 131
1
vote
1
answer
47
views
How can EXP^P be characterized?
I had a question about EXP^P (EXPTIME with access to a P oracle). I thought I had read somewhere that EXP = EXP^P, and that seemed fairly intuitive to me: I thought "adding polynomial power to ...
0
votes
0
answers
20
views
Toda's Theorem generalized to Mod-classes
The proof of Toda's Theorem shows (apart from the fact that $\mathbf{PH} \subseteq \mathbf{P}^{\mathbf{PP}[1]}$) that $\mathbf{PH} \subseteq \mathbf{BPP}^{\oplus\mathbf{P}}$ by using the Valiant-...
- 1
1
vote
1
answer
89
views
Breakdown of the Space Hierarchy Theorem
Say that we have two deterministic space complexity classes $SPACE(n^k)$ and $SPACE(f(n))$ where $f(n) = n^{k-1}$ when $n$ is odd and $f(n) = n^{k+1}$ when $n$ is even. Obviously, if $f(n)$ were ...
- 33
0
votes
1
answer
35
views
If two time complexity classes are equal what does that imply about the time complexity classes for corresponding proper complexity functions?
Say that two complexity classes are equal, i.e. TIME(n) = TIME(nlogn). Does this imply that for some proper complexity function ...
- 33
1
vote
1
answer
40
views
Why is $\mathsf{P} \subseteq \oplus \mathsf{P}$?
I have a very basic question. $\mathsf{P}$ is the class of decision problems solvable in polynomial time by a Turing machine. $\oplus \mathsf{P}$ is the class of decision problems solvable by an NP ...
- 13
1
vote
1
answer
46
views
Is "deterministic non polynomial time" the same as "non deterministic polynomial time"? [duplicate]
I have always though that NP consists of problems solved in a non polynomial time by a deterministic Turing machine. Recently I discovered that NP classifies all the problems solved by a non ...
- 11
0
votes
0
answers
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 ...
- 1
0
votes
1
answer
21
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 ...
- 3
2
votes
0
answers
58
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 ...
- 197
3
votes
1
answer
96
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.
- 53
1
vote
1
answer
40
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 ...
- 113
3
votes
1
answer
103
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 ...
- 690
1
vote
1
answer
27
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?
- 115
1
vote
1
answer
85
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. (...
- 358
2
votes
1
answer
32
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 ...
- 59
0
votes
1
answer
47
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(...
- 221
1
vote
1
answer
57
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 $...
- 2,824
0
votes
0
answers
23
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^...
- 2,824
0
votes
0
answers
63
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
1
answer
61
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$?
- 2,824
0
votes
0
answers
42
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}...
- 225
1
vote
0
answers
19
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? ...
- 49
4
votes
0
answers
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. ...
- 5,704
2
votes
0
answers
34
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 ...
- 203
3
votes
1
answer
137
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,976
4
votes
1
answer
114
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?
- 413
1
vote
0
answers
47
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).
...
- 135
0
votes
1
answer
104
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 ...
- 135
0
votes
1
answer
29
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 ...
- 659
1
vote
1
answer
171
views
How to prove that one problem belongs to class P?
Is there any formal method to prove that one problem belongs to Complexity Class $\mathbb{P}$?
For example, how can we prove that the problem of finding $n^k$ belongs to Class $\mathbb{P}$? We can use ...
- 157
2
votes
1
answer
154
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 ...
- 21
-1
votes
1
answer
73
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 ...
- 2,824
1
vote
1
answer
60
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 ...
- 1,543
0
votes
1
answer
75
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 ...
- 17
1
vote
1
answer
47
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 ...
- 413
1
vote
1
answer
79
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 ...
- 3,512
1
vote
1
answer
23
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 ...
- 3,512
1
vote
0
answers
44
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 \...
- 21
3
votes
0
answers
55
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$, ...
- 31
0
votes
1
answer
21
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,824
2
votes
0
answers
43
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 ...
- 21
2
votes
1
answer
150
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?
- 248