Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
472
questions
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 ...
- 391
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 ...
- 13
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 ...
- 141
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 ...
- 353
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 ...
- 13
-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 ...
- 143
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 ...
- 23
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 "...
- 61
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?
- 29k
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 ...
- 511
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/...
- 135
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 ...
- 8,258
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 ...
- 358
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 ...
- 143
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.
- 53
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 ...
- 700
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. (...
- 358
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(...
- 219