# Tagged Questions

22 views

### Verifier and Certificate for coNP SUBSET-SUM

The original SUBSET-SUM problem is "given a set of integers, is there a non-empty subset whose sum is zero?" If we look at the inverse problem: "given a finite set of integers, does every non-empty ...
70 views

### Proving Hamiltonian Cycle is NP Complete

I'm trying to learn Complexity classes.I want to show Hamiltonian cycle is NP Complete. The text tells me that Inorder to prove NP-Completeness we first show it belongs to NP,by taking a ...
21 views

### Trying to prove something in complexity

I just started to learn about complexity-theory, and I'm trying to prove this: If P=NP, then every (non-trivial) language in P is NP-complete. Can someone give me a solution please?
83 views

### Mixed Q horn SAT

I am familiar with Horn formula: Formula whose clauses have atmost one positive literal. I am also familiar with Mixed Horn formula: Formula whose clauses are either 2 CNF or Horn. Question 1: But, ...
28 views

### Polynomial Reduction for restriction

I ran across a polynomial reduction that used the fact that one language was a restriction of the other. Is that statement really true? $$L_1 \subseteq L_2 \rightarrow L_2 \leq_{p} L_1$$ Thanks!
47 views

### Relation of encryption to P, NP, and NP-Complete

After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ...
66 views

### What does psuedo-polynomial algorithm for subset sum problem mean?

Help me out here - just trying to better understand what 'psuedo-polynomial' means... If the input to an NP-Complete problem is 100 items(ie n=100), and the 'target' is the actual value '100'(t=100): ...
66 views

### Prove 2-HamiltonianCycle $\in \textbf{NP}$

Just want to verify that I have the right idea here with this hamiltonian cycle question. $HC$ = $\{\langle G \rangle$ | $G=(V,E)$ is an undirected graph such that there is a simple cycle (no vertex ...
707 views

### Why is Dantzig's solution to the knapsack problem only approximate

For a bunch of items with values $v_i$ and weights $w_i$, and with a total weight $W$ that our bag can carry, how do we achieve maximum total value without breaking the bag? Dantzig proposed that we ...
14 views

643 views

### Two $NP$-complete languages whose union is in $P$?

I've been thinking about transformations on $NP$-complete problems that produce languages known to be in $P$. However, I can't seem to find an example of two $NP$-complete languages whose union is in ...
139 views

### NP-hardness reduction

Although I know the notion of polynomial time reduction since many years, I am currently confused about the following problem. In a reduction from 3-SAT to 3-Coloring, one constructs (in polytime) a ...
272 views

### Polynomial-Time reduction: Clique Problem

Here is an exercise my friend proposed to me: Show that the maximum clique problem polynomial time reduces to the maximum independent set problem. Here is my attempt at solving it: It is known ...
194 views

### Using Polynomial-Time Reduction to Prove Hardness

From what I understand of polynomial-time reduction, there are two instances of it: many-one and Turing. Many-one simply breaks down problem A into many instances of problem B, and uses the (known) ...
413 views

### NP-Completeness of Certain Bounded Degree Graphs

I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems. 1) L = set of all (G, k) where G is a graph with ...
588 views

### P or NP-Complete? (concerning 2-CNF formulas)

I have two languages that I want to either prove is in P or NP-complete. 1) 2-CNF formulas where there exists an assignment that satisfies the 3/4 of the first 1000 clauses and all of the rest. 2) ...
136 views

### Connect 4 - SAT

My question is about how the Hasbro game Connect4 can be viewed as a SAT problem. My initial guess is that it would actually be QSAT, and that the 'problem' would be something along the lines of: "Is ...
238 views

### Proving NP-completeness intuition

When approaching a problem in NP, initially not knowing whether the problem is in P or NP-complete (or some other choice). It seems to me the only way one can go about "solving" this problem is to ...
175 views

### Proving NP-completeness (hardness) exercises

I am looking for a list of exercises that can be done to practice polynomial time reductions to prove NP-hardness of problems. I know there are hundreds (thousands?) of problems proven to be NP-hard. ...
868 views

### Why is integer factorization considered to be in NP if a quantum computer can compute a factorization in polynomial time?

Sorry if this seems off topic, the cstheory guys told me it was off topic over there, and sent me here. Shor's algorithm on a quantum computer can solve an integer factorization problem in polynomial ...
111 views

### Polynomial-time reduction

How can I prove it? $A \le_p B \Leftrightarrow \overline{A} \le_p \overline{B}$. $A \in \mathcal P \Leftrightarrow \overline{A} \in \mathcal P$. $\overline{A} = \Sigma^* \setminus A$
210 views

### Is Turing completeness monotone with respect to Cook reductions?

I think the post title is relatively clear assuming I worded it correctly, but since I was thinking of a specific example: The language of Boolean expressions is Turing complete; Does this imply that ...
232 views

### complexity theory: consequences of P vs NP

I have a basic question regarding the ramifications of P vs NP. If P=NP, then SAT would be in P. If I understand the definitions correctly, this would imply that there is a Turing machine which ...
8k views

### What is the 3SAT problem?

I don't get the 3SAT problem. Can someone explain the 3SAT problem as if I were 5 years old, ideally with examples? Thanks!
503 views

### Is this partition problem strongly NP-complete?

The Partition problem is weakly NP-complete: Given a set A of positive integers, can A be partitioned into two disjoint subsets with the same sum? I'm interested in the hardness of this variant: ...
1k views

### Is coNP closed under Kleene star?

Is coNP closed under Kleene star operation? I have the answers, in which they say it is possible to build a graph that describes all possible divisions of the string in which the sub-words are in in ...