Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
5,282
questions
0
votes
0
answers
55
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 ∨ ...
- 176
0
votes
1
answer
66
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))$.
...
- 203
0
votes
1
answer
48
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
58
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 ...
- 203
0
votes
1
answer
74
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
72
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
25
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
0
votes
0
answers
37
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 ...
- 203
1
vote
1
answer
41
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 ...
- 203
1
vote
1
answer
54
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
28
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 ...
- 123
1
vote
1
answer
38
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
53
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
48
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
58
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 ...
- 123
0
votes
1
answer
75
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
142
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
33
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
154
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
137
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,790
0
votes
1
answer
105
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
80
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
31
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
43
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
31
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
57
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
37
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
46
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
25
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
59
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
42
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
147
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
106
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
31
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 ...
- 176
0
votes
2
answers
61
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 $...
- 125
1
vote
1
answer
150
views
Why NP is not certain subset in P/poly?
Complexity class P/poly includes languages, which cannot be calculated by means of classic Turing machine, including unary halting problem
However, class NP is relatively simple, can be calculated via ...
- 113
1
vote
0
answers
25
views
About infinite languages in RE and coRE
Let $L \in RE$. Then $L$ might be finite or infinite.
I assume this is also true for $coRE$.
But, if I have a language $L \notin RE$, it necessarily means that $L$ is infinite, am I correct?
Also, if $...
- 37
0
votes
2
answers
86
views
How to show a language is in NP?
(I reorganized my question.)
We have a function $f$ mapping the integers $\{1, . . . , 2^k\}$ ONTO the integers $\{1, . . . , 2^k \}$ such that when these integers are represented in binary, and $f$ ...
- 3
1
vote
1
answer
60
views
Difference between function and search problems?
I am a bit confused on what the difference between a "function problem" and a "search problem" is.
The specific problem I have been studying is known as End-Of-The-Line:
Given two ...
- 111
0
votes
1
answer
54
views
Is this variant of #Positive 2-SAT #P-complete?
This variant of #Positive 2-SAT is defined as follows :
We are given a set of variables :
(a,b,c,d,e)
we can form our 2-literal clauses from these set of variables but we want the input in this ...
- 33
1
vote
0
answers
29
views
Listing all subsets of size $k$ of $\{1,2,...,n\}$ with just $C \binom{n}{k}$ operations
I was wondering if it is possible to list all subsets of size $k$ of the set $\{1,...,n\}$ by performing at most $C \binom{n}{k}$ operations for a fixed constant $C$.
I did find a way to compute these ...
- 11
0
votes
0
answers
17
views
Can a PTAS be called one if it is parameterized by one of the problem inputs (in addition to ε)?
I.e. is it right to say "a PTAS parameterized by sth"?
Is it unusual, and is it correct?
- 1
0
votes
2
answers
221
views
Can a DFA have multiple of the same state?
I need to create a DFA for a sequential order of states e.g.
A -> B -> C -> B -> A
and so on, where 'A' is the start and finish state,
1 is a transition to the next state and 0 just loops ...
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