Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

Filter by
Sorted by
Tagged with
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 (...
Dannyu NDos's user avatar
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\}^*$ ...
KJL's user avatar
  • 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 ...
Zeeshan ahmed's user avatar
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} = \...
Zeeshan ahmed's user avatar
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 ...
PPP's user avatar
  • 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 ...
gfunk's user avatar
  • 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{...
Straw User's user avatar
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.} & \...
Ramon's user avatar
  • 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 ...
Anuj's user avatar
  • 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,...
SlowerPhoton's user avatar
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 ...
Anuj's user avatar
  • 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 ...
Samuel Bismuth's user avatar
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 ...
dino-t's user avatar
  • 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 ...
Samuel Bismuth's user avatar
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\...
Turbo's user avatar
  • 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 $...
Erel Segal-Halevi's user avatar
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 ...
dino-t's user avatar
  • 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 ...
dino-t's user avatar
  • 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 ...
Erel Segal-Halevi's user avatar
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 ...
Daniil Kozhemiachenko's user avatar
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}$) ...
nuss_ecke's user avatar
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 ...
FANNYG's user avatar
  • 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 ...
mathquester's user avatar
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 ...
sbluff's user avatar
  • 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 ...
Polgerta's user avatar
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 ...
AsksQuestions's user avatar
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 ...
Ariel Yael's user avatar
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 ?
user157446's user avatar
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 ...
l4m2's user avatar
  • 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 ...
nosyarg's user avatar
  • 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-...
Hjm's user avatar
  • 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 ...
Hjm's user avatar
  • 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 ...
Sidharth Ghoshal's user avatar
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 ...
thiaamak's user avatar
-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 ...
wij's user avatar
  • 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 ...
Samuel Bismuth's user avatar
-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 ℕℙ. ...
wij's user avatar
  • 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 ...
Alonso Montero's user avatar
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 ...
getraparth's user avatar
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{...
kostrykin's user avatar
  • 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$,...
Heda Chen's user avatar
  • 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 ...
Würthi's user avatar
  • 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 ...
Würthi's user avatar
  • 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 ...
user56834's user avatar
  • 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 ...
aghx99's user avatar
  • 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 ...
Nicola Carrassi's user avatar
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 ...
Ondolin's user avatar
  • 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 ...
user777's user avatar
  • 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?
Hendrik Jan's user avatar
  • 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 ...
Xavier Labouze's user avatar

1
2 3 4 5
10