Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
5,340
questions
4
votes
0
answers
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, ...
18
votes
4
answers
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
0
votes
0
answers
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
1
answer
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$ ...
- 531
0
votes
0
answers
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
2
answers
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-...
2
votes
1
answer
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
3
votes
0
answers
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
0
votes
0
answers
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
0
votes
0
answers
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
0
votes
1
answer
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
0
votes
1
answer
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 ...
0
votes
1
answer
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
0
votes
1
answer
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 ...
- 145
2
votes
1
answer
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
0
answers
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
...
-3
votes
1
answer
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
2
answers
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
1
answer
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
0
votes
0
answers
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
1
answer
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 ...
- 251
0
votes
0
answers
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 ...
- 133
1
vote
1
answer
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
0
votes
0
answers
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 ...
- 1
2
votes
2
answers
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
0
votes
1
answer
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
2
answers
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
0
answers
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
0
votes
0
answers
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 ...
- 133
0
votes
1
answer
88
views
Knapsack with no capacity
Given a set $S$, a value function $v(s)$ and a cost function $c(s)$ for all $s \in S$, and integers $B$ and $K$, the classic formulation of the Knapsack problem asks if there is a subset $S' \subseteq ...
3
votes
2
answers
147
views
An algorithm that is $O(n^{\log(n)})$
After having searched for a while, and after having read this
https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities
I was just wondering: is ...
- 131
1
vote
0
answers
44
views
How to develop intuition to come up with Context Free Grammar?
So i'm taking this class automata and complexity at georgia tech and we were given practice material for our exam.
one of the question is to give context free grammar for these two languages
and the ...
- 11
0
votes
2
answers
177
views
Complexity of generating all subsets of size $k$ using recursion
What is the complexity of the following (Python) code, that builds the list L of all subsets of size $k$ of a given set?
...
- 125
3
votes
1
answer
138
views
Does a problem remain tractable If a single discrete variable becomes continuous?
Let $\mathcal{F}$ be a family of pairs of the form $(A,b)$, where $A$ is an integer matrix and $b$ is an integer vector with the same number of rows. For every integer $k$, define $L(\mathcal{F}, k)$ ...
- 5,730
0
votes
1
answer
108
views
Ackermann Decision Problem
I have been studying the Ackermann function, specifically the two-argument Ackermann–Péter version.
With the Ackermann function, I developed a problem I call the "Ackermann Decision Problem"
...
- 143
0
votes
1
answer
83
views
Possible reduction from SUBSET-SUM
Given is a multiset $S$, a finite set $T = \{t_1, t_2, t_3\}$, and an integer $k \in \mathbb{N}$.
Let $v(t_j)$ be a set of values $\in \mathbb{R^+}$ of length $|T|$ that can be assigned to $s_i$, and $...
0
votes
0
answers
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 ...
0
votes
0
answers
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
1
answer
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
0
votes
0
answers
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
1
answer
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. ...
- 87
0
votes
1
answer
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
1
answer
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 ...
- 251
0
votes
0
answers
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
0
votes
1
answer
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
1
answer
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 ...
- 13
0
votes
1
answer
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
1
answer
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
0
answers
33
views
what is the worth of non-read once Branching Programs?
In Harvard CS 221 Computational Complexity, Lecture 3, it introduced Branching Programs
A branching program is a DAG that
has 1 start node and 2 output nodes with out-degree 0, labelled 0 and 1. Each ...
- 318
0
votes
2
answers
65
views
Unlimited use subset sum
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 $...
