# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

5,201 questions
Filter by
Sorted by
Tagged with
1 vote
117 views

### How to prove that this problem is NP-complete (or NP-Hard)

I have the following data: A set $V$ of tasks, the starting time $s_j$ of each task and the duration $p_j$ of each task. A set $K$ of resource, each resource has an availability function $R_{k}$ ...
43 views

### Selecting a submatrix of a binary matrix NP hard?

I have the following problem and I am wondering if it is NP Hard or not. Let $A$ be a binary matrix whose rows and columns are indexed by the sets $\mathcal{I}=1,...,m$ and $\mathcal{J}=1,...,n$. A ...
13 views

### Color a a general graph with maximal degree $\Delta$ using $2^{O(\Delta)}$ colors within $\log^{*}n$ rounds

Consider the following algorithm $A$ to 6-color an rooted tree within $\log^{*}n$ rounds in a distributed system: 1: Assume that initially the nodes have IDs of size $\log(n)$ bits 2: The root is ...
48 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 ∨ ...
1 vote
37 views

### Why do simple Logical Gates have an Irrational amount of Bits?

Suppose $2$ bits are used to encode a message, A and B. If you know $A$ is $1$, you have one bit of information. If you know $A\land B$ is $1$, you have two bits of information. If you know $A\land B$...
2k views

### In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the ...
30 views

### On proving the uncomputability of Kolmogorov complexity by contradiction

I have seen a proof by contradiction for the uncomputability of Kolmogorov complexity. The idea the basically the same as in the proof for halting problem (i.e., there are cases that lead to Berry ...
267 views

### Constructing equivalent (to a polynomial-time degree) decision problems from function problems

Let's say we're some function problem, $R \subseteq \Sigma^* \times \Sigma^*$, where $\Sigma = \{0, 1\}$ and some oracle $O_R$ that solves $R$. Now, we're given some language, $L \subseteq \Sigma^*$ ...
26 views

### Can you transform 3sat (or equivalent) into another satisfiability problem that increases the ratio of solutions to non-solutions

Say I have f(x1,x2,x3,...) where the output is either 0 for all inputs (unsatisfiable) or a variable boolean output of 0 or 1 depending on the input (satisfiable). Let's not consider functions that ...
1 vote
144 views

### Is the number of NP-complete problems finite?

It should be straight forward to show that there are infinitely many NP-hard problems: Proof: Take the problem Remove 1 Vertex 3-COL ($R1V3COL$) which takes a graph $G=(V,E)$ as an instance and ...
1 vote
65 views

### Integrality gap and complexity classes

I would like to know if there exist some complexity classes that are defined according to the integrality gap of their problems? In particular, is there a class of problems for which their integrality ...
139 views

### Can protein folding destroy cryptography?

They say that protein folding is an NP-hard problem, meaning that if we could figure out how any protein folds, we could solve any NP problem in polynomial time. However, doesn't this basically ...
57 views

### If X is poly-time reducible to Y and X is in P, then Y is in P

The answer I found on the Internet is false. But my argument is that if I know that X is poly-time reducible to Y, which means I can use Y as a sub-routine to solve X, i.e., if I have a blackbox of Y ...
1 vote
166 views

### Question about how can i determine if counting sort is the right option over other sorting algorithms

So, an exam's exercise asks me to find an alghoritm that can determine if counting sort is the best solution, otherwise use another optimal sorting algorithm. Now i find that solutions for that ...
1 vote
64 views

117 views

216 views

### Question about the Relativization barrier

Baker, Gill, and Solovay has shown in their famous paper, that there are oracles $A$ and $B$ with $P^A = NP^A$ and $P^B \not= NP^B$. So, one can't solve the $P$ vs. $NP$ Problem with methods like ...
221 views

### Weakest reduction for P-completeness

It is common to define $P$-completeness with respect to logspace many-one reductions. I am looking for a complexity class $C$ such that if $C=P$ then all problems in $P$ are $P$-complete under many-...
30 views

### Hardness of the bin packing problem

I have been reading up on the bin packing problem. In the bin packing problem, we are given $n$ items with sizes $a_1,a_2,\dots, a_n$ such that $$1 > a_1 \geq a_2 \geq \dots \geq a_n > 0$$ The ...
1 vote
20 views

### Class of optimization problems whose decision versions are in P

NPO is defined to be the class of optimization problems whose decision versions are in NP. I would like to get the complexity class of optimization problems whose decision versions are in P. Is such ...
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)$ ...