Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

Filter by
Sorted by
Tagged with
0 votes
1 answer
26 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
15 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
0 votes
0 answers
45 views

PP and the most significant bit of functions in #P

I've found the following sentence (and some variants) in a lot of places, namely in Arora and Barak's Computational Complexity: A Modern Approach. Intuitively, PP corresponds to computing the most ...
1 vote
1 answer
33 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 ...
1 vote
0 answers
73 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
25 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 ...
0 votes
0 answers
16 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
30 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 ...
  • 239
1 vote
1 answer
24 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
55 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-...
  • 37
-1 votes
1 answer
53 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 ...
  • 37
0 votes
1 answer
69 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 ...
1 vote
1 answer
33 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 ...
-4 votes
2 answers
125 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
41 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 ...
-2 votes
2 answers
146 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
38 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 ...
2 votes
1 answer
31 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 ...
2 votes
1 answer
89 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
28 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$,...
  • 191
1 vote
2 answers
33 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
52 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,472
1 vote
1 answer
78 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 ...
  • 43
0 votes
0 answers
38 views

Definition of NP within an implementation of deterministic TMs

I am currently writing a mathematical definition for the deterministic Turing Machine so I can make use of it in one of my papers. (below, I will use the term "tuple" as a synonym for "...
0 votes
1 answer
43 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
55 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
37 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
571 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?
2 votes
1 answer
212 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 ...
1 vote
1 answer
43 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/...
3 votes
1 answer
295 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 ...
1 vote
0 answers
15 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 ...
2 votes
0 answers
29 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
60 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 ...
1 vote
1 answer
92 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
45 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
51 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
112 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
37 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
34 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
149 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 ...
  • 199
3 votes
1 answer
124 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.
1 vote
1 answer
52 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
169 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 ...
1 vote
1 answer
30 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
95 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. (...
2 votes
1 answer
38 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
48 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(...

1
2 3 4 5
10