Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
491
questions
1
vote
0
answers
28
views
What's the intuition behind MIP* being bigger than MIP?
It is well-known that $\mathsf{MIP} = \mathsf{NEXPTIME}$, and recently there was a breakthrough stating that $\mathsf{MIP^*} = \mathsf{RE}$.
This was very confusing because it seemed like the (...
- 335
0
votes
1
answer
23
views
$NL$ Leaf languages and $PSPACE$
I am reading Papadimitriou's Computational Complexity and got stuck on part d) of the following exercise (pg. 505)
20.2.14 A panorama of complexity classes. ... A language $L \subseteq \{0, 1\}^*$ ...
- 3
1
vote
0
answers
46
views
How to prove MIP is in NEXP
I was trying to understand the proof of MIP is inside NEXP. I was referring to Rutger's university scribes (link). They define MIP as a class with exponential proof, but that is not the definition I ...
0
votes
0
answers
23
views
Is PAD(EXP) = P?
Can I say that all languages in the class $\textbf{P}$ are just a padded version of some other problem in $\textbf{EXP}$?
I am familiar with the padding argument, which states that if $\textbf{P} = \...
0
votes
3
answers
87
views
Time complexity of GPU computing
The time complexity of the matrix product is $O(n^3)$ if calculated normally for each element.
If computed on GPU, is it $O(n)$?
What I thought:
GPU can compute each element of the matrix product in ...
- 3
0
votes
1
answer
79
views
Discrepancy in Time-Complexity of Bounded Halting Problem
Can you please help identify if the two following variants of the bounded halting problem are in different deterministic complexity classes?
$$
H1 = \{ (\langle M \rangle, w, t) \mid \text{$M$ accepts ...
- 103
0
votes
0
answers
75
views
Proving EXP-Completeness for the Bounded Halting Problem
I am currently working on proving that the bounded halting problem is $EXP$-Complete. The bounded halting problem is defined by the language $L$ as follows:
$$L = \{\langle M,x,t \rangle : \text{...
1
vote
1
answer
74
views
NP-Complete Proof - Using CFLP
I have formulated the below optimization problem.
\begin{align}\nonumber
\hspace{-3mm}&\text{(P) minimize}\!\sum_{i}\!\alpha_{i}w_{i}\!+\!\sum_{i}\sum_{j}\!c_{ij} p_{ij}\!\\
\text{s.t.} & \...
- 15
0
votes
1
answer
76
views
Complexity of this variant of #Positive 2-SAT #P-complete?
In this variant of #Positive-2-SAT ,we divide set of all possible clauses like this :
A = [ab ,ac ,ad ,.... ]
B =[bc ,bd ,be ,....]
C=[cd ,de ,....]
D=[de ,....]
....
In this variant ,we are allowed ...
- 33
0
votes
1
answer
53
views
How is P not trivially equal to ZPP?
The definition of ZPP seems to be
$$ZPP = RP \cap coRP.$$
I think ZPP should then be equivalent to P, because for any language L in ZPP, there is an algorithm A and B proving that it is in RP and coRP,...
- 169
0
votes
1
answer
487
views
Complexity of a variant of #Positive-2-SAT
#Positive-2SAT is the problem of counting the number of satisfying assignments to a given Positive 2-CNF formula i.e 2-CNF formulas in which each literal is a positive occurrence of a variable.
The ...
- 33
1
vote
1
answer
80
views
Integrality gap and complexity classes
I would like to know if there exist some complexity classes that are defined according to the integrality gap of their problems?
In particular, is there a class of problems for which their integrality ...
- 127
1
vote
1
answer
53
views
Lower Bound on Parity of Boolean Functions
Let's say we have boolean functions $f_1, \cdots, f_n$, each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show ...
- 13
1
vote
0
answers
23
views
Class of optimization problems whose decision versions are in P
NPO is defined to be the class of optimization problems whose decision versions are in NP.
I would like to get the complexity class of optimization problems whose decision versions are in P.
Is such ...
- 127
0
votes
0
answers
33
views
Does $PP\subseteq BPP$ imply $PP\subseteq RP$?
Consequence of $\mathsf{NP\subseteq BPP}$ to $\mathsf{NP\subseteq ZPP}$? clarifies $NP\subseteq BPP\implies NP\subseteq RP$.
What about for $PP$? Does $PP\subseteq BPP$ imply $PP\subseteq RP$ and $PP\...
- 2,881
3
votes
0
answers
123
views
Is there a class for optimization problems with polynomial-time-computable bounds?
An optimization problem can be described by two functions $f$ and $g$, such that:
$f$ is a binary predicate representing the constraints: $f(x,y)$ is True if the output $y$ is feasible for the input $...
- 5,720
0
votes
1
answer
24
views
P/poly and dyadic oracle
If we let a language L in {0,1}* be dyadic if for each x in L, and each index i with xi = 1, i is a power of 2, then consider the class of languages recognized by a polynomial time oracle machine with ...
- 13
0
votes
0
answers
15
views
Relativizations/Oracles for the BPP and RP complexity classes
If we consider the complexity classes RP and BPP, then to show RPBPP = BPPRP my first thought is we need to use some kind of majority voting to amplify our success probabilities. The issue is I don't ...
- 13
1
vote
1
answer
62
views
Decision version of optimization problems with polynomial-time approximation algorithms
Given an optimization problem $X$, it is easy to construct a decision problem $Y$, such that there is a two-directional polynomial-time reduction between $X$ and $Y$.
Therefore, we can define a class ...
- 5,720
1
vote
1
answer
305
views
Unions of PSPACE-comlete problems that are PSPACE-complete?
Let $A,B\subsetneq\Sigma^*$ be PSPACE-complete problems for some fixed $\Sigma$ such that $A\cup B\neq\Sigma^*$ and $A\cup B\in\mathrm{PSPACE}$. Does it follow that $A\cup B$ is PSPACE-complete?
In ...
3
votes
0
answers
55
views
Is there such a thing as $coW[1]$-hardness?
I have a problem $\mathsf{A}$ and I would like to analyze its (parameterized) computational complexity.
I found a parameterized reduction from the complement of the independent set ($\mathsf{coIS}$) ...
- 31
0
votes
1
answer
28
views
Let A, B two languages such that A=B does that implies that coA=coB
I'm getting to a problem while studying my computability and complexity exam.
If two languages A and B, such that A=B does that implies that coA=coB?
And in general if two language are describe by ...
- 1
0
votes
0
answers
57
views
What's the meaning of Borodin's Gap Theorem?
In complexity theory we have Borodin's theorem as follows:
I do not get what the consequence is. So, wikipedia told me that there are arbitrarily large gaps between the complexity classes.
Isn't that ...
0
votes
0
answers
21
views
Complexity Class theorization
Being C a complexity class, if C is contained in its complementary class, does it imply that the C = coC?
So far I tried to prove $C \subseteq coC \implies C \subseteq coC \land coC \subseteq C$.
I ...
- 1
1
vote
1
answer
77
views
Correct defintion polynomial-time reduction
I have frequently seen two different definitions of polynomial-time reduction. In the following let $A, B \subseteq \Sigma^*$ be decidable problems. I will try to formulate the definitions in my own ...
- 13
1
vote
0
answers
77
views
Alternative outcomes of P versus NP
Given what we know, which of the following scenarios are possible:
There exist algorithms which are in-fact Ptime algorithms for NP-Complete problems, but which cannot be proved to work.
and there ...
2
votes
0
answers
27
views
Are $\mathsf{L,NL}$ closed under reverse operation?
for a language $L$ we define $rev\left(L\right)=\left\{ \sigma_{n}\cdot\ldots\cdot\sigma_{1}\mid w=\sigma_{1}\cdot\ldots\cdot\sigma_{n}\in L\right\} $.
My question is, are $\mathsf{L,NL}$ closed under ...
- 141
0
votes
0
answers
19
views
Protocol Proposed by Arthur-Merlin, and Zero Knowledge
Why there is a need for Arthur Merlin protocol.
What are the cause and differences between arthur-merlin protocol and Zero knowledge protocol ?
1
vote
0
answers
35
views
How can $R_HL$ differ from $RL$?
https://complexityzoo.net/Complexity_Zoo:R
RL: Randomized Logarithmic-Space Has the same relation to L as RP does
to P. The randomized machine must halt with probability 1 on any
input. It must also ...
- 249
1
vote
1
answer
38
views
What Complexity Class Contains $QSAT_{\log n}$?
It is known that $QSAT$ is $PSPACE$ complete, and it is known that $QSAT_i$ is $\Sigma_i$ complete for any constant $i$. However, what if we had $QSAT_{\log n}$? That is, $QSAT$ where the quantifiers ...
- 115
0
votes
2
answers
92
views
Ιf 3SAT reduces to its complement then NP=coNP
Can you please explain to me why the following is true?
Ιf 3SAT reduces to its complement then NP=coNP.
Thoughts:
3SAT is NP-complete so for every X in NP
$X \leq 3SAT$
$\overline {3SAT} $ is NP-...
- 47
-1
votes
1
answer
235
views
EXACT INDSET is DP-complete
The class DP is defined as the set of languages L for which there are
two languages $L1 \in NP$ , $L2 \in coNP$ such that $L = L1 \cap L2$. (Do not
confuse DP with $NP \cap coNP$, which may seem ...
- 47
0
votes
1
answer
95
views
Is there a standard name for the complexity class "embarassingly parallel"
So i'm defining the embarassingly parallel complexity class as the set of decision problems which can be solved in time $O(T(n))$ on a single computer and in time $O(T(n)/g(n))+O(\log(g(n))$ if you ...
- 353
1
vote
1
answer
73
views
What is the name of the complexity class for the optimization version of co-NP-complete and coNexpTime-complete problems?
I know that the optimization version of NP-complete problems belong in NPO. What about co-NP-complete problems? Is there a co-NPO class, or is it just NPO?
I've also never seen the name for the ...
- 23
-4
votes
2
answers
132
views
About a ℙ≠ℕℙ proof
Executable: Sat prog
Definition: The exit status of "Sat prog" is 1 iff there exists an instance
prog arg which runs in P-time and the exit status is 1.
From the definition, Sat computes ...
- 3
0
votes
0
answers
44
views
Approximation Class that Decides
Suppose we have a minimization ILP. Denote its value by $OPT$.
Let $PER$ be the solution to its LP relaxation.
Given a real number $t$, we would like to decide whether $OPT \leq (1+t) \cdot PER$, in ...
- 127
-2
votes
2
answers
149
views
A (False) Proof That ℙ≠ℕℙ
Why the following proof is invaid?
Using C-like pseudo-program:
Definition: bool S(Func, UInt): S(f,n)==true iff ∃x, x<=n, F(x)==true
F is defined in ℙ as a certificate function, so S is in ℕℙ.
...
- 3
3
votes
0
answers
42
views
Given a complexity class C for problems which can be solved using exponential time and an exponential number of random bits. C ⊆ NEXP?
There must be a complexity class C that includes exactly the problems that can be solved in exponential time and having access to a truly random coin (which in turns implies that you will be able to ...
- 145
2
votes
1
answer
37
views
Can you define a complexity class by giving a language and declaring that the language is complete for the class?
Can I define a complexity class $\mathsf{C}$ by giving a language $L^\prime$ and stating that $L^\prime$ is $\mathsf C$-complete? Specifically, a language $L$ is in $\mathsf C$ if there is a reduction ...
- 23
2
votes
1
answer
218
views
What is the (intuitive) relation of NP-hard and #P-complete problems?
From Wikipedia on $\mathrm{NP}$-completenes: "a [decision] problem is NP-complete if it is both in NP and NP-hard." [link] I think we can paraphrase this as the first statement:
An $\mathrm{...
- 123
1
vote
1
answer
41
views
construct language in ${\sf BPP \backslash (RP \cup coRP)}$ assuming $\sf RP \neq ZPP$
Problem
This is a HW problem from CMU 15-455 (hw10, p1(a)), spring 17 by Ryan O'Donnell.
Assume $L \in {\sf RP \backslash ZPP}$. Define
$$ L' = \left\{ (x, y) : \text{either $x \in L$ and $y \notin L$,...
- 301
1
vote
2
answers
41
views
Can all non-quantum physical systems be efficiently simulated on a classical computer?
Is it true that simulating classical physical systems is in P, i.e. can be done efficiently on Turing machines or are there known exceptions? I'm thinking of chaotic systems but I'm also curious more ...
- 141
2
votes
1
answer
25
views
I'm trying solve a problem using different versions of SAT, how exactly does mixing SAT affect the hardness of the problem?
I'm trying to solve a problem which I can solve in 3SAT or as a mixed 2,3,4 SAT. I know how hard each of those categories are individually and know the derivations of their hardness individually. But ...
- 141
2
votes
1
answer
56
views
Is there a theorem of the form "for any complexity class $C$ satisfying $X$, there exist $C$-complete problems"?
From what I've read, there are $C$-complete problems for all the complexity classes $C$ that I have looked at: $P$, $NP$, $EXPTIME$, $PSPACE$. But I also know that there is an infinite hierarchy of ...
- 3,632
2
votes
1
answer
145
views
Difference between "almost-linear" and "quasilinear" time complexities
In some works, such as the recent maxflow paper, there is reference to an "almost-linear" complexity, which typically refers to a complexity of $O(n^{1+o(1)})$.
This is similar to the notion ...
- 53
0
votes
1
answer
53
views
Given the current knowledge about complexity class, what can we say?
I am a CS student. I am looking at some questions my professor made and I got stuck in this one.
"Which one of the following inclusions between complexity classes is coherent with the current ...
0
votes
0
answers
61
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 ...
- 119
1
vote
1
answer
45
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 ...
- 729
1
vote
2
answers
718
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?
- 29.8k
2
votes
1
answer
253
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