# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

5,282 questions
Filter by
Sorted by
Tagged with
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 ∨ ...
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))$. ...
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 ...
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
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
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 ...
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 ...
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 ...
75 views

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 ...
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
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 ...
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 ...
1 vote
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. ...
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 ...
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 ...
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 ...
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？
1 vote
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 ...
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 ...
1 vote
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 ...
1 vote
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 ...
61 views

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$ ...
1 vote
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 ...
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 ...
1 vote
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 ...
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?
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 ...