Skip to main content

Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

Filter by
Sorted by
Tagged with
2 votes
1 answer
40 views

Question regarding definition of dIP

I was self-studying Interactive Protocols from Introduction to Computational Complexity by Arora, Barak. Initially, we define when we say a language $L \subset \{ 0,1 \}^*$ is a k round deterministic ...
Rishabh Kothary's user avatar
0 votes
0 answers
23 views

Do large integers increase the expressiveness of $\mathsf{SUBSET-SUM}$?

We can consider any set $A$ of integers as a nondeterministic "subset-sum circuit" for strings represented as numbers in some range $[-2^N, 2^N]$, accepting an integer $n$ within this range ...
user171764's user avatar
2 votes
1 answer
75 views

Why would the existence of a sufficiently strong PRNG prove P=BPP?

The $P$ vs $BPP$ question is often explained as such: if there exists a "strong enough" PRNG, we can use it to derandomize any randomized algorithm. However, I don't get how this, let's call ...
Mike Battaglia's user avatar
3 votes
1 answer
47 views

Is $\text{BPP}$ the largest polynomial-time "tractable" complexity class?

An algorithm is in $\text{BPP}$ if it is a) guaranteed to halt in polynomial time, and b) gives the right answer with some probability $p > 0.5$ independent of the input. $\text{BPP}$ is ...
Mike Battaglia's user avatar
0 votes
1 answer
24 views

4COL problem with additional constraint on the size

The task is to prove that that 4-coloring of a graph with additional constraint about number of vertices is NP-complete. Constraint: Each color class should contain at least $ \frac{1}{5}$ of total ...
Abel's user avatar
  • 51
1 vote
2 answers
58 views

Up to a certain number of witnesses, say 4

For a language $L$ to be in $NP$ it suffices for a witness $y$ to exist and a (polynomial) verification algorithm $A$, s.t. $x\in L$ iff there exists a (polynomial size) $y\,$ s.t. invoking $A$ on $x,...
Benicio Agüero's user avatar
2 votes
1 answer
103 views

A paradox about cardinality of ALL and arithmetic hierarchies ― Did I just prove that ZFC is inconsistent?

This problem arose when I tried to find the arithmetic hierarchy that $\mathsf{ALL}$, the class of all formal languages over a finite alphabet, corresponds to (like how $\mathsf{R} = \Delta^0_1$ and $\...
Dannyu NDos's user avatar
2 votes
0 answers
37 views

Complexity class BPP, but with only expected polynomial running time

The complexity class BPP requires that the running time be guaranteed polynomial, though with only a 2/3 chance of the correct output. ZPP, on the other hand, guarantees correct output, but now only ...
Mike Battaglia's user avatar
3 votes
1 answer
339 views

Prove that "max independent set is larger than max clique" is NP-Hard

We define B as: $B = \{ <G> | \text{ G is an undirected graph in which} \\ \text{the number of vertices in the largest independent set} \\ \text{is greater than the number of vertices in the ...
shaggy's user avatar
  • 77
3 votes
0 answers
45 views

P and RP - what if a Turing machine accepts on almost all paths?

The Wikipedia page on the RP complexity class says: An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic Turing machines where ...
Erel Segal-Halevi's user avatar
2 votes
1 answer
41 views

Relation between ExpTime vs Pspace

Are there any EXPTIME-COMPLETE problems that cannot be proven to be PSPACE-COMPLETE?
jaime bonilla's user avatar
2 votes
1 answer
64 views

Does NSPACE($n^2$) $=$ DSPACE($n^4$)?

From Savitch's Theorem, we know that NSPACE($n^2$) $\subseteq$ DSPACE($n^4$), but does the other direction hold? As far as I understand all we can say is that DSPACE($n^4$) $\subseteq$ NSPACE($n^4$).
BreadthFirstTreeSearchFan's user avatar
5 votes
1 answer
66 views

Is it known whether EXP is contained/not-contained in P/log?

Checking the complexity zoo (https://complexityzoo.net/Complexity_Zoo:P), I can only read that "if NP is contained in P/log then P = NP", so, right now, there must be no proof for EXP ...
441Juggler's user avatar
1 vote
0 answers
21 views

$\mathsf{NP}$ vs. $\mathsf{coNP}$ and sparse sets

Consider the following statement: If there exists a sparse set of negative (the ones whose answer is no) instances $I$ such that for every negative instance $a$ ...
rus9384's user avatar
  • 1,781
0 votes
0 answers
11 views

Disjunctively Self-Reducible Languages and Their Relationship to NP

Can anybody help me in solving this question mentioned below.
pro's user avatar
  • 1
1 vote
1 answer
66 views

NP, NP-Hard and NP-Complete

If a problem S is NP-Complete and we know that a problem Q is polynomial time reducible to S. Does that mean that Q belongs to NP? Also, when can we state that Q is NP-Hard but does not belong to NP? ...
Shreyas Shrawage's user avatar
1 vote
2 answers
206 views

The SAT problem can be reduced to the complement of the halting problem?

The SAT is in NP, I suppose that the complement of the halting problem is in coNP-hard. I suppose the answer is no because SAT is not in coNP, but I am not sure.
knorbika's user avatar
0 votes
1 answer
40 views

The problems in the P class can be polynomially reduced to its complement and vica versa?

I considered the Euler circle problem to decide this. The polynomial reduction is: I add a new vertex in the graph: If the degree of each vertex is even, then I connect all the vertices with this new ...
Andrew19's user avatar
1 vote
2 answers
72 views

$A$ and $B$ two decision problems.If $A\le\ B$ then $\overline{B}\le\overline{A}$ is true?

I have proved that $\overline{A}\le\overline{B}$ is true, but I have no idea how to prove or disprove the opposite direction.
Andrew19's user avatar
1 vote
1 answer
26 views

We know that there is an algorithm for a problem that decides it in $\Omega(2^n)$ time. We know that it is not in P class, or we cannot decide?

I know that exists problems that surely cannot be decided in polynomial time because P class doesn't equal with EXPTIME (for example Go, generalized chess etc.). But I assume that there may be ...
Andrew19's user avatar
2 votes
1 answer
52 views

Is there an NP-hard problem that is polynomially reducible to its complement, and whose complement is polynomially reducible to the problem?

I suppose that this statement is true if NP equals with coNP, otherwise not, but I don't know how can I prove that.
knorbika's user avatar
0 votes
2 answers
118 views

Is there a decidable problem that we know for sure cannot be solved in polynomial time?

If yes, could you say an example? P=NP would result in NP problems being solvable in polynomial time, but there would still be problems in the EXPTIME class.
knorbika's user avatar
0 votes
1 answer
48 views

The Hamiltonian cycle problem is P-hard?

I know what P-hard means. Let's denote the P-hard problem as H. For any problem A in P, there exists a polynomial-time reduction from A to H. I think the answer is yes (I suppose that every "easy&...
knorbika's user avatar
3 votes
2 answers
690 views

Is 2-coloring in NL or L?

The 2-coloring problem is in P. How can I prove that it is in NL or L? I see that I should create a deterministic/nondeterministic algorithm with logarithmic space, but I have no idea how to store ...
knorbika's user avatar
1 vote
0 answers
52 views

Is it known, whether the complement of NP-hard problems is necessarily again NP-hard?

Neither could I find any counterexamples, nor could I show that if indeed the complement of NP-hard problems was NP-hard, one could deduce some unknown results from it, which would imply that it is ...
LostBetweenTheLines's user avatar
1 vote
1 answer
41 views

Using time hierarchy theorem to show $Time(n^7)$ strictly contained in P

I'm relatively new to computational complexity and am trying to use the time hierarchy theorem to show that $Time(n^7)$ is strictly contained in P. I understand that the time hierarchy theorem says ...
Lucas's user avatar
  • 11
1 vote
0 answers
86 views

Complexity of a variant of the Subset Sum Problem (second level polynomial hierarchy)

What is the complexity class of the following variant of the SSP problem: Input: set of integers $\{x_1,\ldots,x_n\}$, integer $k$ and integer $T$. Output: Yes, if there exists a subset $S\subseteq \{...
user3445340's user avatar
2 votes
0 answers
18 views

Properties of $\mathsf{PH}[1]$ and $\Sigma^{\mathsf P}_{poly(n)}[1]$?

$\mathsf{PH}[1]$ is a variant of a polynomial hierarchy in which each machine can only call its oracle once. $\Sigma^{\mathsf P}_{poly(n)}[1]$ is a polynomially "tall" tower of $\mathsf{NP}[...
rus9384's user avatar
  • 1,781
6 votes
1 answer
282 views

Are any "standard" complexity classes uncountably infinite?

(This is a somewhat fuzzy question.) I believe that most of the "standard" complexity classes that one comes across in complexity theory are countably infinite, because they are defined in ...
tparker's user avatar
  • 1,116
1 vote
1 answer
23 views

How is $\mathsf{RP\cap UP}$ not a class containing only unsatisfying languages?

$\mathsf{RP}$ can be deterministically defined as: A language $L\in\mathsf{RP}$ iff there exists a polynomial $p$ and deterministic Turing machine $M$, such that: $M$ runs for polynomial time $p$ on ...
rus9384's user avatar
  • 1,781
2 votes
0 answers
42 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
1 vote
1 answer
35 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
  • 13
2 votes
0 answers
84 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 ...
Zee's user avatar
  • 243
0 votes
0 answers
26 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} = \...
Zee's user avatar
  • 243
1 vote
3 answers
196 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
  • 13
1 vote
1 answer
113 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
  • 113
1 vote
0 answers
144 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
108 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
79 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
  • 43
1 vote
1 answer
129 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
510 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
  • 43
1 vote
1 answer
95 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
2 votes
1 answer
77 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
  • 23
1 vote
1 answer
45 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
3 votes
0 answers
125 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
26 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
  • 23
1 vote
1 answer
85 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
311 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
4 votes
1 answer
93 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
30 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

1
2 3 4 5
11