# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

3,739 questions
Filter by
Sorted by
Tagged with
2 views

### Subset sum to 0/1 knapsack

Show how an arbitrary instance (S, t) of Subset Sum can be translated into (i.e. reduced to) an instance of 0-1 Knapsack. Clearly indicate how the profits, weights, and capacity are determined. Hint: ...
33 views

### Restriction: polynomial time decision of instance is why needed to “decision Problem”?

I am reading book "combinatorial optimization 3rd edition(Bernhard Korte、 Jens Vygen)". (latest version is sixth.) There are some discriptions in this book that I don't understand Not all binary ...
505 views

### Assuming P != NP, what is the cardinality of the set of NP-Hard languages?

If P=NP, then every non-trivial language is NP-Hard, so clearly there are uncountably many NP-Hard languages. However it's less clear to me what the cardinality of this set is assuming P != NP.
26 views

### Unlimited size proof in PCP versus limited size

I have the exact same question as this guy, except I don't agree with the "verified" answer. Since in his answer the one to one mapping he describes depends on the input it makes the verifier $V'$ not ...
512 views

### How to prove graph isomorphism is NP?

I know that Graph Isomorphism should be able to be verified in polynomial time but I don't really know how to approach the problem. Any help would be appreciated.
105 views

### How do I reduce subset sum to another problem in NP?

I'm trying to solve the following problem about arranging pens on rows. The problem goes as the following. Given $n$ integers $l_1, \dots l_n$, the lengths of the pens, r rows and a goal G. Is it ...
16 views

41 views

### Reduce duplicate subset sum problem to distinct subset sum problem?

In duplicate subset sum problem (DuSSP), we are given a multiset $\{a_1,a_2,\ldots,a_n\}$ where some of the $a_i$ are duplicates. We can assume that $a_1\leq a_2\leq \cdots\leq a_m.$ We are also given ...
65 views

### If A is polynomial time reducible to B and B is in NP, then A is in NP

If $A\leq_p B$ and $B$ is in $NP$, is it true that $A$ is in $NP$? What about : "if $A\leq_p B$ and $B$ is in $coNP$, then $A$ is in $coNP$"? Thanks in advance. I think both hold. If $B$ is in $NP$...
17 views

### First attempt at convert Context-Free Grammar into Chomsky Normal Form

This is my first attempt at converting a context free grammar into chomsky normal form. I think I have the correct answer, would just appreciate any feedback if I have gone wrong somewhere. Context ...
80 views

### Is GAP NP-hard with at most two balls per bins?

The generalized assignment problem (GAP)  is given by: Instance: A pair $(B,S)$ where $B$ is a set of $m$ bins (knapsacks) and $S$ is a set of $n$ items. Each bin $j∈B$ has a capacity $c(j)$, and ...
22 views

### What is the complexity class of performing a perfect disassembly of binary code?

I have heard that the complexity class of performing a perfect disassembly of binary is undecidable. Is this correct? Are there any proofs of this?
14 views

### What are the requirements for a superset of P to be closed under karp reductions?

So today in our exercise session on complexity theory we discussed that P, NP, and BPP are closed under karp reduction. We also figured that the proofs could likely be expanded to straight ...
72 views

### Is “Extended Church-Turing Thesis” the same as “Cobham-Edmonds Thesis”?

I have been looking for any reference regarding the term: "Extended Church-Turing Thesis" [some people will call it, Strong Church–Turing Thesis]? Does anyone defined it or it is just people in ...
Let $G$ be a simple complete graph with an edge-2-coloring. An alternating Hamilton (x,y)-path is a Hamiltonian path which starts at vertex $x$ and ends at vertex $y$ such that the colors of its ...