# Questions tagged [np]

Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.

752 questions
Filter by
Sorted by
Tagged with
130 views

### If Q* can break encryption would that prove P=NP?

At 12:11 in this video the creator talks about unverified rumors the Q* algorithm can break AES-192 encryption. If this is true, would this mean P = NP?
31 views

### Pseudopolynomials and $NP$ problems like $CLIQUE$

Having encountered the concept of "pseudopolynomials", my understanding is that we have to be careful when the input to a problem is a number, that the complexity of the solution should be ...
30 views

### Is « Does exist at least one function $u$ such that $f(u(0)) \ne g(u(0))$? » an NP problem? or a P problem?

$f$ and $g$ being known functions. We suppose that the problem is solvable. To me, for the moment, this question, if a decision problem it is or can be, is more an NP rather than a P problem, because ...
1 vote
37 views

### Subset sum reducible to barter economy problem?

I was given the following problem called the barter economy problem: Given a set of $n$ people $\{p_1, \ldots, p_n\}$ and a set of $m$ distinct objects $\{a_1, \ldots, a_m\}$, where each object $a_j$ ...
38 views

### Is the class NP closed under complement? (Follow-up)

As a follow up to this question already been asked here, I was wondering - if we supposed that P != NP, would then the following reasoning be correct: In NP problems we can only verify in poly-time ...
43 views

### Constructing an SAT formula from a Clique graph

We were given this practice question to do in a lecture and its solution afterwards. I have spent hours upon hours trying to understand the solution but still do not understand. From my knowledge when ...
18 views

### Can irreversibility show that P ≠ NP?

Can the fact that there are irreversible operations show that P ≠ NP? In other words: Why can't the existence of one-way functions be proven?
1 vote
41 views

### Why is infeasibility of linear programming considered to be an NP problem?

I recently came across this question, and the way I think people usually go about this is to find a certificate that answers 'yes' to the decision problem 'Is this LP infeasible?' Or, given a ...
4k views

### Why are computability problems always written in full caps?

Maybe this is an odd question. It has always bugged me that computability problems are written in all caps, and in such an "awkward" way. SAT, 3-SAT, COLORING, 3-COLORING, PARTITION, CLIQUE, ...
87 views

### Is NP=RP(2^-n)?

I believe its true but struggle to prove. I know NP=union over positive c's of RP(2^-(n^c)) and from here to prove that RP(1/2^n) contained in NP is immediate. the other side is the problem. I've ...
31 views

### If I want to prove that a problem is in NP, can the vertifier use exponential space?

I want to prove that a problem is in NP. I have a witness (of polynomial size), and a verifier that runs in polynomial time. However, this verifier uses exponential space, becuase it has to generate ...
39 views

### Investigating the Claim: co-$NP\subseteq NP\text{/}P$ implies $\Sigma_3^P=\Pi_3^P$ and Collapse of the Polynomial Hierarchy?

I have been studying the polynomial hierarchy recently, and I came across an intriguing claim that I would like to explore further: Assuming co-$NP\subseteq NP\text{/}P$, the claim states that it ...
1 vote
163 views

### What could $P = NP$ imply about arbitrary Turing machines?

My question: What $P \not= NP$ or $P = NP$ could imply about arbitrary Turing machines and arbitrary computations? I assume that a partial and incomplete, but objective answer to this question exists ...
36 views

### SMALL-FACTOR is not NPC. Is the statement true or false?

Given the SMALL FACTOR problem where: INPUT: an integer N and an integer k OUTPUT: yes ⇐⇒ N has a prime factor ≤ k. I know that SMALL-FACTOR problem ∈ in NP ∩ CO-NP. If it were NP-Complete we would ...
1 vote
44 views

75 views

### How to provide a reduction from 3SAT to domatic number problem

How to provide a reduction from 3SAT to domatic number problem. Domatic number problem: Given a graph $G = (V, E)$ and an integer $k$, can we partition $V$ into at least k disjoint sets of vertices, ...
1 vote
49 views

### Hardness of the k-center problem with relaxed triangle inequality

Consider the $k$-center problem where we are given an undirected, complete graph $G=(V, E)$, with a distance $d(u, v) \geq 0$ for each pair $u, v \in V$. Furthermore, we assume that the triangle ...
6k views

### False proofs that look correct

I remember seeing a list of False Proofs when I was taking Discrete Maths and I found it to be very interesting and also helpful. So, if anyone knows some common proof mistakes students make or some ...
20 views

### reduction from partition to N3DM or balanced 3 partition problem

I want to know how can I reduce Subset Sum or Partition problem to N3DM problem in which each set has exactly 3 elements and same sum. N3DM Problem: https://en.wikipedia.org/wiki/Numerical_3-...
1 vote
41 views

### P NP R RE closures

I wrote the following table for all the closures in those classes. is anything there incorrect? also, would appreciate help with coNP and coRE closures. couldn't find much information about it online.
1 vote
148 views

### is the class NP closed under set difference?

I know P is closed under all Boolean operations, but what about NP? is NP closed under set difference and symmetric difference? is this table accurate? Edit: updated table:
65 views

### Can all NP-complete problems be reduced to NP?

I know that by definition, all NP problems can be reduced to NP-Complete problems. But does that also applies the other way around? Can all NP-Complete be reduced to NP problems? My understanding is ...
97 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
23 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 ...
67 views

### Finding a Polynomial Time algorithm for the 3-SAT Problem

Let us consider m clauses containing 3 variables each i.e. A1,A2,A3...Am . Let the total literals in consideration be n. Then each clause : Ai = (xr $\lor$ xs $\lor$ xt) where 1 $\le$ r,s,t $\le$n and ...
21 views

### Construct polynomial-time algorithm to decide whether there is a linear classifier containing all points in X and no points in Y [duplicate]

Consider n-dimensional linear classifiers, that is, subsets of R n that have the form {(x1, x2, . . . , xn)| a1x1 + a2x2 + · · · + anxn ≥ b} for some real numbers a1, . . . , an and b. Given as input ...
16 views

### Analogue of NP for oracle problems

I was just reading this question on the quantum computation stack exchange. It asks whether the HSP is in NP or not, and the answer notes that NP is a class of languages, not oracle problems. The ...
85 views

### Showing there exists a polynomial-time algorithm for deciding the existence of a linear classifier

For this question I figure we need to define a system of linear inequalities which I thought could be something like this : a1x1 + a2x2 + ... + anxn ≥ b if (x1, x2, ..., xn) ∈ X a1x1 + a2x2 + ... + ...