Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

Filter by
Sorted by
Tagged with
1 vote
1 answer
59 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
167 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
39 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
69 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
51 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
44 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
666 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
50 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
39 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
85 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,632
6 votes
1 answer
273 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,096
1 vote
1 answer
22 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,632
2 votes
0 answers
37 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
30 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
63 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
144 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
99 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
117 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
89 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
78 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
97 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
498 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
91 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
75 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
0 answers
28 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
40 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,891
3 votes
0 answers
124 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
25 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
0 votes
0 answers
20 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
  • 23
1 vote
1 answer
76 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
310 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
87 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
29 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
22 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
121 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
28 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
1 vote
0 answers
46 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
43 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
  • 232
0 votes
2 answers
137 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
273 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
1 vote
1 answer
102 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
106 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
137 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
154 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

1
2 3 4 5
11