# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

5,340 questions
Filter by
Sorted by
Tagged with
39 views

### Interactive proof for PSPACE-hard problems different from QBF

The celebrated proof that IP = PSPACE relies on an interactive proof for the QBF problem. Is there any other "natural" interactive proof for a PSPACE-hard problem other than QBF? (of course, ...
2k views

### Measuring time complexity in the length of the input v/s in the magnitude of the input

I know that formally the time compliexity of an algorithm is measured in the length of the input, which in binary would be the number of bits required to encode the input. The problem that I have with ...
• 183
28 views

### $BQP$ vs $NP$ in the unlikely scenario of $PH=PSPACE$

It is known that: ${\sf BQP} \subseteq {\sf PSPACE}$ and ${\sf PH} \subseteq {\sf PSPACE}$. If tomorrow its proven that ${\sf PH} = {\sf PSPACE}$ it would also imply ${\sf BQP} \subseteq {\sf PH}$. ...
• 753
1 vote
27 views

### Constrained precedence parsing

This is a simple variation on precedence parsing for which I haven't been able to prove the existence of an efficient algorithm. Is this a known problem? The setup is as follows: we are given $n$ ...
41 views

### How do Turing machines output $f(w)$ for $O(1)$ reductions?

When speaking about many-one Karp reductions, the definition is stated below: $$A \leq_P B \iff \exists f \colon \: \Sigma^* \mapsto \Gamma^* \: \text{such that} \: (w \in A \iff f(w) \in B)$$ where ...
• 153
1 vote
303 views

### Can the optimization version of a problem be NP-hard while its decision version is in P?

I have formulated an instance of a 0-1 Integer Program (IP), which I am trying to determine the complexity of (can this instance be solved in polynomial time or not). As we know, the 0-1 IP is NP-...
60 views

### Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$

I often hear NP-completeness as problems such that, if they were in $P$ all problems in $NP$ are in $P$. The true definition, though, is that NP-complete is a set of languages in NP that all languages ...
• 153
135 views

### Are any known problems complete for $P$ under "$O(1)$ reductions?"

The usual many-one reduction involves Turing machines transforming an input, $w$, of some language to an input, $f(w)$, of some other language in polynomial time. (Where $w \in L_1 \iff f(w) \in L_2$)....
• 153
30 views

### Why doesn't the problem of determining whether a word has the same number of 0's and 1's prove $P \neq L$?

One big problem in complexity theory is $P$ vs $L$. I was just thinking about why this isn't trivial, and I came up with the following example. Of course, it cannot work as a proof as it seems too ...
• 153
56 views

### Why weakening rule doesn't increase the size of resolution refutation?

I am studying the complexity of SAT resolution refutation. There is a useful tool named weakening rule The weakening rule: B -->B ∨ C says that from a clause B we can derive the weaker clause B ∨ ...
• 318
67 views

### Does $\texttt{DTIME}(O(1))$ contain only finite languages?

My question is pretty much just the title. It is pretty easy to see that any finite language can be solved in $O(1)$ time. For this reason, every finite languages is in $P$, $L$, and $DTIME(O(1))$. ...
• 213
49 views

### Converting P = NP into an effective equivalence algorithm

If P = NP, then is it the case that there exists a total recursive function from the set of polynomial-time nondeterministic Turing machines to the set of polynomial-time deterministic Turing machines ...
61 views

### Why aren't promise problems just decision problems; can't we encode the promised inputs in the alphabet?

I don't really understand why promise problems are classified differently than decision problems. Consider this problem as an example. Given some real number between $0$ and $1$, determine if it ...
• 213
102 views

### Given a boolean circuit that computes a boolean function, can we always find an equivalent circuit with optimal size?

Let's say that we have a decision problem $P$. Let's also say that $I_n$ is the set of all instances of size $n$ that exist for this problem, and that its cardinality is finite. There is a sequence of ...
78 views

### Is the clique decision problem in co-NP?

Is the clique decision problem in co-NP? Definitions: "In the clique decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph ...
• 23
1 vote
31 views

### How to show that my problem cannot be approximated within a certain factor unless P=NP?

Before I introduce my problem I need to define a couple of things. Suppose we have two sets $S_1=\{1,2,3\}$ and $S_2=\{2,3,4\}$. A compression tree for $S_1$ and $S_2$ is ...
74 views

### Why is this not a proof of P # NP

Suppose that there is a set of strings such that for each n there is at most one string |w| = n. For any given n there is a 50:50 chance that such a string exists. These string can be arranged in a ...
• 21
1 vote
73 views

### Are there problems in NP that would solve P vs NP, but are not NP complete

NP-complete problems are the "hardest problems" in NP. This means that all other problems in NP reduce (in polytime) to these problems. A consequence of this is if we were to find some ...
• 213
1 vote
47 views

### Given a bipartite graph G and an integer l, how many edge subsets of size l are there such that the degree of each vertex is odd?

Given a bipartite graph $G=(V,E)$ and an integer $l$, how many edge subsets ($E'\subseteq E$) of size $l$ are there such that the degree of each vertex in the resulting subgraph $G'=(V,E')$ is odd? I ...
• 133
34 views

### Reduction between problems where problem A solves problem B with probability $\frac{2}{3}$

Suppose we have a problem, $A$, and a machine $T_A$ that solves $A$. Now, let's say we have a problem $B$ that is solvable with a polynomial number of calls to $T_A$, and we call $T_B$ the machine ...
• 213
1 vote
55 views

### Chaitin’s version of Gödel’s theorem and pseudorandomness

Chaitin’s version of Gödel’s theorem roughly states that there exists a constant c such that for each string of one’s and zeroes x, the sentence “the algorithmic information complexity (Kolmogorov ...
41 views

### If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$

I have the problem If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$ To solve this I am using a result $BP\cdot NP\subset NP/poly$ which I can prove (not doing here). I have two solutions but ...
1 vote
41 views

### Ford-Fulkerson algorithm running in pseudo-polynomial time

Consider a graph with $n$ nodes and $m = \mathcal{O}(n^2)$ edges. The maximum capacity among all edges is denoted by $C$. The running time is given by: $\mathcal{O}(nmC)$ If I consider the input size ...
• 11
33 views

### Finding the Optimal Palette for a Set of Images

Motivation I want to draw pictures using indexed colors. As I have limited space for colors per-palette, I want to choose palettes in an intelligent fashion, based on the pictures I want to draw. The ...
57 views

### Is there a common notation for describing this operation $coNP\; ? \; NP = DP$?

While working with complexity classes, I've come along the definition of $DP$ (or $D^p$): $$DP = \{L_1 \cap L_2 \mid L_1 \in NP \text{ and } L_2 \in coNP\}$$ I am interested in a different (and much ...
• 301
59 views

### Prove that the problem MATCH is NP-complete

The problem MATCHED is defined as follows: given an infinite set S of strings of arbitrary length over the alphabet {0, 1}, determine if there exists a character of length n over the alphabet {0, 1} ...
1 vote
59 views

### Explanation of Cook-Levin Suitable for First Years

TLDR; Looking for Explanation of Cook-Levin theorem palatable to CS first years who are theory averse I'm a prof. teaching first year algorithms+programming and want to give my students a taste of ...
• 11
1 vote
19 views

### Does adding a polynomial-time function impact APX-hardness?

I have two optimization problems $A$ and $B$, and I recently managed to show that there exist functions $f$ and $g$ that are computable in polynomial time, such that for any instance $x$ of $A$ there ...
• 11
26 views

### Why $rank(C|_V)\geq rank(C)$ for $r$-rank preserving subspace for depth 3 circuits

I was reading Deterministic Black Box PIT Testing for Generalized Depth 3 Arithmetic Circuits - Karnin and Shpilka In the Theorem 3.4 they told $rank(C|_V)\geq rank(C)$ We have $C|_V$ which is ...
88 views

54 views

### Simulating 2D Turing Machine Page onto a 3 tape turing machine

If I have a 2D Turing machine, how would I go about simulating this onto a multi-tape (k=3) turing machine? I have these math properties that are supposed to help me: Consider a function φ : N2 → N ...
58 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 ...
1 vote
32 views

### I would like to know what are the directions to work on if I want to prove that $NP=coNP$?

I am currently learning about NP and coNP related content and have been exposed to the$NP \overset{\text{?}}{=}coNP$ problem. I would like to know what are the directions to work on if I want to prove ...
• 305
58 views

### Complexity of this variant of $positive -⊕2SAT$?

This is like a follow up question from my previous post about complexity of $positive -⊕2SAT$. The problem positive $⊕2SAT$ is defined as a problem where we need to find the parity of the number of ...
• 33
1 vote
39 views

### The extent of NP-Completeness

I am told that if a decision problem that is in NP Complete can be solved in polynomial time, then P=NP. However, would this mean that we would instantly have an algorithm to solve any NP problem. ...
48 views

### Complexity of this variant of $⊕2SAT$?

The problem $⊕2SAT$ is defined as a problem where we need to find the parity of the number of solutions of $2$-$CNF$ formulae and is known to be $\oplus P$ complete. I introduce the following variant ...
• 33
1 vote
85 views

### Non rigorous argument that $P \ne NP$ implies $avgP \ne distNP$

Consider the following nonrigorous argument that $P \neq NP$ implies $avgP \neq distNP$. (For those unfamiliar with the latter complexity classes, they deal with average case hardness.) Suppose A is ...
33 views

### If the polynomial hierarchy collapses to level 1, what is the significance?

Recently, I was studying polynomial hierarchy and found that many unsolved problems are related to it, such as $P=NP$,$NP=coNP$. I would like to ask, if the polynomial hierarchy collapses, what does ...
• 305
80 views

### If $NP^{NP} = NP$, then the polynomial hierarchy collapses to it's first level. How to prove it?

From this link Does $NP^{NP}=NP$? I learned that if $NP^{NP} = NP$, then the polynomial hierarchy collapses to it's first level. But how to prove it？
• 305
1 vote
43 views

### Subquadratic multiplication of polynomials in the max-plus/tropical semiring

Is there an algorithm to multiply two polynomials with coefficients in the max-plus semiring $(\mathbb{Z}\cup\{-\infty\}, \max, +)$ which is faster than the trivial one? I'm interested in the ...
194 views

### Is maximal independent set on maximal planar graphs still NP-complete?

We know that finding the size of the maximal independent set of a planar graph is NP-complete. I'm curious about whether it remains NP-complete for maximal planar graphs, i.e., the graphs in which ...
• 25
1 vote
166 views

### 3-Dimensional Matching $\leq$ $_{p}$ subset sum Explanation

excuse me, could someone explain to me the reduction of the problem 3-dimensional matching to subset sum? I was reading Jon Kleinberg's design algorithms book and when I came across this reduction I ...
• 11
1 vote
Given a finite set of integers $Z$ and a number $z$, I would like to check if there exists a subset $A=\left\{ a_1,...,a_{\left| A\right|}\right\}\subseteq{Z}$ and a set of $\left| A\right|$ numbers \$...