Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

Filter by
Sorted by
Tagged with
0 votes
0 answers
44 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 ...
user avatar
  • 109
1 vote
1 answer
27 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 ...
user avatar
  • 719
1 vote
2 answers
510 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?
user avatar
  • 27.6k
2 votes
1 answer
121 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 ...
user avatar
1 vote
1 answer
28 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/...
user avatar
3 votes
1 answer
201 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 ...
user avatar
1 vote
0 answers
14 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 ...
user avatar
2 votes
0 answers
22 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 ...
user avatar
  • 131
1 vote
1 answer
47 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 ...
user avatar
0 votes
0 answers
20 views

Toda's Theorem generalized to Mod-classes

The proof of Toda's Theorem shows (apart from the fact that $\mathbf{PH} \subseteq \mathbf{P}^{\mathbf{PP}[1]}$) that $\mathbf{PH} \subseteq \mathbf{BPP}^{\oplus\mathbf{P}}$ by using the Valiant-...
user avatar
1 vote
1 answer
89 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 ...
user avatar
  • 33
0 votes
1 answer
35 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 ...
user avatar
  • 33
1 vote
1 answer
40 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 ...
user avatar
  • 13
1 vote
1 answer
46 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 ...
user avatar
0 votes
0 answers
26 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 ...
user avatar
  • 1
0 votes
1 answer
21 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 ...
user avatar
  • 3
2 votes
0 answers
58 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 ...
user avatar
  • 197
3 votes
1 answer
96 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.
user avatar
1 vote
1 answer
40 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 ...
user avatar
  • 113
3 votes
1 answer
103 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 ...
user avatar
1 vote
1 answer
27 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?
user avatar
  • 115
1 vote
1 answer
85 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. (...
user avatar
2 votes
1 answer
32 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 ...
user avatar
  • 59
0 votes
1 answer
47 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(...
user avatar
1 vote
1 answer
57 views

What is the comparator circuit?

The standard circuits $AC^i$, $NC^i$ are constructed using $AND$, $OR$ and $NOT$ of various fan-ins, fan-outs and depths. What is the comparator gate constituted from? Structurally why is it believed $...
user avatar
  • 2,824
0 votes
0 answers
23 views

What is the depth of comparator circuit required in Gale Shapely and STCONN?

Stable matching problem and $STCONN$ can be solved using comparator circuits (refer https://arxiv.org/abs/1208.2721). What is the depth of the $CC$ circuit necessary for stable matching? Is it in $CC^...
user avatar
  • 2,824
0 votes
0 answers
63 views

A paper claiming that optimization version of symmetric TSP can be solved in polynomial time

In the following paper : Czopik, J. (2019) An Application of the Hungarian Algorithm to Solve Traveling Salesman Problem. American Journal of Computational Mathematics,9, 61-67. In the Introduction, ...
user avatar
1 vote
1 answer
61 views

Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?

Let $C$ be an uniform complexity class for example $NL$ or $NP$. Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
user avatar
  • 2,824
0 votes
0 answers
42 views

Is this combinatorial seach problem NP-complete?

The context: Consider the following optimization problem. Let $f_1,\dots,f_L:\mathbb{R}\to\mathbb{R}$ arbitrary (continous) functions for $L>1$ and $x_k\in\mathbb{R}$ evolve according to $$ x_{k+1}...
user avatar
1 vote
0 answers
19 views

$W$-hierarchy and parameterized search problems

I have two related questions: What are the ways to prove that a certain problem is in $W[t]$ in the W-hierarchy for parametrized complexity, except using the straight definition of boolean circuits? ...
user avatar
4 votes
0 answers
34 views

What is a term for a problem that is hard to approximate within a factor $c$?

Let $f$ be a maximization problem. If there is a reduction from SAT to the following problem: "given an integer $c$, decide if there is an $x$ for which $f(x)\geq c$", then $f$ is NP-hard. ...
user avatar
2 votes
0 answers
34 views

Rigorous Definition of a Complexity Class

From Wikipedia, "Complexity classes are sets of related computational problems. They are defined in terms of the computational difficulty of solving the problems contained within them with ...
user avatar
3 votes
1 answer
137 views

Polynomial time optimization problems belong to which complexity class?

I know that $\mathsf{P}$ class is only defined for decision problems. Therefore, a problem like "Does there exist an $(s,t)$ path of length $k$ in the graph $G$?" is in $\mathsf{P}$. One can ...
user avatar
4 votes
1 answer
114 views

How to prove that existence of one-way functions implies P≠NP?

Wikipedia: The existence of such one-way functions... would prove that the complexity classes P and NP are not equal. How is this proved?
user avatar
  • 413
1 vote
0 answers
47 views

Consequence of NP-complete, and DP-complete w.r.t. randomized reductions

If a problem is NP-complete with respect to randomized (polynomial time) reductions, but not with respect to deterministic reductions, then we have P $\neq$ BPP (See Question 2 here and its answer). ...
user avatar
0 votes
1 answer
104 views

Different definitions of complexity class DP

I would like to know how different defintions of class DP (also written $D^p$) are equivalent (brief explanations would do). The following are the two definitions I see: Difference between two NP ...
user avatar
0 votes
1 answer
29 views

Are problems that are fractions of constraints of NP-complete problems also NP-complete?

We know that Hamiltonian path, clique and independent sets are NP-complete but what about half or the square root of each problem or a fraction of $n$ ? That is, for a graph, $G$ of $n$ nodes, is ...
user avatar
1 vote
1 answer
171 views

How to prove that one problem belongs to class P?

Is there any formal method to prove that one problem belongs to Complexity Class $\mathbb{P}$? For example, how can we prove that the problem of finding $n^k$ belongs to Class $\mathbb{P}$? We can use ...
user avatar
  • 157
2 votes
1 answer
154 views

How does strong NP-completeness agree with encoding complexity?

I've recently read about the concepts of weak and strong NP-completeness, but faced a problem in wrapping my head around them. I've understood that problems which have numerical parameters (like ...
user avatar
-1 votes
1 answer
73 views

What is the relation between $USAT$, $UP$ and $NP=RP$?

Definition: AtmostONESAT: SAT instance having promise of $\leq1$ witness. What is the complexity consequence if an instance of $SAT\in$ AtmostONESAT can be decided whether or not there is a witness in ...
user avatar
  • 2,824
1 vote
1 answer
60 views

Randomized Version of NP

I came across interactive proofs and randomized computation, in particular, i read about the complexity classes $\text{IP}, \text{BPP}, \text{RP}$, etc. Since the above classes are well-known, I will ...
user avatar
0 votes
1 answer
75 views

$coNP$ and $\oplus P$?

Let a non-deterministic machine have at most $2^{t+1}-1$ accepting paths (highest significant bit position is $t$ and lowest significant bit position is $1$). I want to decide if the number of ...
user avatar
1 vote
1 answer
47 views

What is the "formula" for "any cipher can be deciphered by a quantum computer"?

There are several quantum complexity classes in different ways analogous to NP: NQP, QMA, and, as I understand, others. P=NP BPP=NP in simple words means "any cipher can be deciphered by a ...
user avatar
  • 413
1 vote
1 answer
79 views

What is the complexity class of finding vertex cover number of a simple graph?

Suppose we have a simple graph $G$. We know that finding the minimum vertex covering set for $G$ is in the NP-hard class. But, what about the complexity class of finding the size of the set, i.e., the ...
user avatar
  • 3,512
1 vote
1 answer
23 views

Is it possible to compute the minimum vertex covering set in quasi-polynomial time, by knowing the vertex cover number?

If we know the vertex cover number for a simple graph $G$ denoted by $\tau(G)$, is it possible to find the minimum vertex cover set for $G$‌ in quasi-polynomial time? As I found, we cannot find any ...
user avatar
  • 3,512
1 vote
0 answers
44 views

An opposite method of padding argument on N/DTIME complexity class

Is there a method to prove things with longer input in complexity theory? For example, using padding argument it's trivial to show that $\text{NTIME}(n^2) \subseteq \text{DTIME}(n^4) \Rightarrow \...
user avatar
3 votes
0 answers
55 views

Sufficient condition for a complexity class's closure under NP-reductions?

Let us say that there exists a $\mathsf{NP}$-reduction from a problem $A$ to another problem $B$ when there exists a non-deterministic, polynomial-time Turing machine $T$ such that for each $a \in A$, ...
user avatar
0 votes
1 answer
21 views

Is $E^{quasiP}$ equal $E$ or larger?

Let $quasiP$ be the quasipolynomial time complexity class. Is $E^{quasiP}=E$ false? Is $E^{DTIME(2^{(\log n)^k})}=E$ false at every $k>1$?
user avatar
  • 2,824
2 votes
0 answers
43 views

Language in PSPACE that isn't PSPACE-hard and isn't in PH

Can there exist a language L in PSPACE such that L isn't PSPACE-hard and L isn't in the polynomial hierarchy (PH)? Intuitively, it seems like the answer is no, since TQBF is PSPACE-complete, and any ...
user avatar
2 votes
1 answer
150 views

What is the definition of Infinitely Often class in complexity

I was reading a paper and I came across the term $L\notin i.o.Dtime(2^{n^c}/n^c)$. What is the meaning of this?
user avatar

1
2 3 4 5
9