Questions tagged [np]

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

Filter by
Sorted by
Tagged with
-3 votes
1 answer
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?
Asleepace's user avatar
0 votes
1 answer
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 ...
CuriosityScream's user avatar
0 votes
1 answer
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 ...
someone's user avatar
1 vote
1 answer
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$ ...
redbull_nowings's user avatar
0 votes
1 answer
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 ...
Meki21's user avatar
  • 11
0 votes
1 answer
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 ...
emily-cs's user avatar
0 votes
0 answers
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?
Geremia's user avatar
  • 148
1 vote
1 answer
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 ...
Namrata Banerji's user avatar
19 votes
2 answers
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, ...
Jul Wac's user avatar
  • 191
0 votes
0 answers
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 ...
Tomer Thaler's user avatar
0 votes
1 answer
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 ...
user606273's user avatar
0 votes
0 answers
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 ...
Straw User's user avatar
1 vote
1 answer
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 ...
Axid Ubish's user avatar
0 votes
0 answers
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 ...
user161646's user avatar
1 vote
1 answer
44 views

What are the necessary requirements for proving NP is closed under complement?

I've had the following question on a test and I answered: 'False', my answer was incorrect and I'm trying to understand why. $VC = \{<G,k> |\ G =$ undirected graph with a vertex cover of size $k\...
Skynet's user avatar
  • 53
0 votes
0 answers
67 views

if it were shown that every algorithm that solves SAT must have complexity Ω(n^(log n)) then P≠NP?

Shouldn't this statement be false? To be true the implication should be P=NP or am I wrong? I can't find a formal proof
PatrickBateman's user avatar
1 vote
0 answers
93 views

if L is in NP-Complete and its complement is also in NP does that mean L is in P? (meaning that P=NP)

$L^\complement$ = the complement of L is it true that if $L\in NPComplete $ and $L\leq_p L^\complement \rightarrow P=NP$ basically asking if the following statements are correct $if (L\in NPComplete ) ...
Skynet's user avatar
  • 53
2 votes
1 answer
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, ...
Hughson's user avatar
  • 21
1 vote
1 answer
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 ...
TheCollegeStudent's user avatar
25 votes
13 answers
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 ...
proof-of-correctness's user avatar
0 votes
0 answers
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-...
user's user avatar
  • 1
1 vote
1 answer
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.
Skynet's user avatar
  • 53
1 vote
1 answer
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:
Skynet's user avatar
  • 53
0 votes
2 answers
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 ...
Joan Marcual's user avatar
0 votes
3 answers
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 ...
Uzair Siddiqui's user avatar
1 vote
0 answers
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 ...
Samuel Bismuth's user avatar
0 votes
0 answers
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 ...
Pathlessbark8's user avatar
0 votes
0 answers
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 ...
AZ689's user avatar
  • 1
0 votes
0 answers
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 ...
Andrew Baker's user avatar
0 votes
1 answer
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 + ... + ...
automatically's user avatar
0 votes
0 answers
37 views

Is PrefixFreeNP=P?

I was given the following definition of a verifier: Verifier $V$ is called $PrefixFree$ if for every $x,y$ such that $V(x,y)=1$, then for every $y'$ (which is not an empty string, $y'\ne\epsilon$) $V(...
MiddleEasternPrince's user avatar
4 votes
2 answers
102 views

Do all NP-hard problems have a reduction from one to another (Either A $\leq_m$ B or B $\leq_m$ A)

Given two problems, $A$ and $B$, that are NP-hard. Is either one of the following is true? $A \leq_m$ B $B \leq_m$ A In other words, is there always a relationship between any two arbitrary NP-hard ...
Andrew Baker's user avatar
0 votes
0 answers
13 views

$NP\subseteq P/poly\implies PH\subseteq P/poly$

We know if $NP\subseteq P/poly$ then $PH=\Sigma_2$ Then We want to show that $\Sigma_2-SAT\in P/poly$. Now $$\phi\in \Sigma_2-SAT\iff \exists\ x\in\{0,1\}^{p_1(n)}\ \forall\ y\in \{0,1\}^{p_2(n)},\ \...
Soham Chatterjee's user avatar
1 vote
1 answer
46 views

Do all P problems reduce to all NPI problems?

It is often said that NP-intermediate problems, such as factoring, graph isomorphism, discrete log, and so on are "harder" than the problems in P. Meaning that they cannot be solved in ...
Andrew Baker's user avatar
0 votes
1 answer
41 views

Do reductions (in NP and other classes) follow a linear path?

NP has several complete problems, which reduce to one another. In this sense, they are all "equal" in terms of hardness. There are other problems in NP that are also "equal" to one ...
Loic Stoic's user avatar
1 vote
2 answers
72 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 ...
Loic Stoic's user avatar
0 votes
1 answer
68 views

Time complexity to convert a truth table to a boolean circuit

The SAT problem is often explained in terms of truth tables. Given some random boolean circuit, calculate its truth table; does there exist an output of $1$ in the truth table? But how about going the ...
Loic Stoic's user avatar
0 votes
0 answers
12 views

Would proving that finding a satisfiable input is intractable prove that SAT is intractable? [duplicate]

With the SAT problem, there is a corresponding search variant. Given an arbitrary boolean expression, find a given input such that the output of the boolean expression is $1$. To my knowledge, this ...
Loic Stoic's user avatar
1 vote
1 answer
32 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 ...
lz9866's user avatar
  • 305
0 votes
0 answers
33 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 ...
lz9866's user avatar
  • 305
0 votes
1 answer
80 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?
lz9866's user avatar
  • 305
1 vote
1 answer
164 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 ...
Emma3201's user avatar
0 votes
2 answers
100 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$ ...
Isak He's user avatar
-1 votes
2 answers
59 views

Is One Way TSP NP-Complete?

I know that finding the optimal solution to One Way TSP (TSP but the salesman does not have to return to his original city) is NP-Hard, but is it NP-Complete? I ask this because I recently found a ...
Darcy Sutton's user avatar
1 vote
1 answer
81 views

Why is 3-co-SAT not in P?

The 3-co-SAT problem consists of deciding whether if a 3CNF formula, has an unsatisfiable assignment of variables, i.e., assignment of variables that evaluates to 0. We know that 3-co-SAT is in coNP, ...
Denizalp's user avatar
0 votes
1 answer
38 views

Is $\overline{A_{TM}}$ co-NP Hard?

I know that $A_{TM}=\{<M,w>|M~is~a~TM~and~M~accepts~w\}$ is NP-Hard: By showing a polynomial time reduction - $A \le_p A_{TM}$: Let $A \in NP$, then there exists a $NTM$ that decides $A$ in ...
Geo's user avatar
  • 37
0 votes
1 answer
72 views

Using undecidability to prove P != NP

Given the challenge of proving algorithmic bounds on the likes of 3-SAT to resolve P versus NP, I wondered whether it might be possible to use undecidability within an NP problem to ensure that we can ...
Brian's user avatar
  • 1
2 votes
1 answer
33 views

Whether the class of languages with time complexity between polynomial and exponential is an NP language?

We know that the P language class is a polynomial-time solvable language class, and the NP language class can be determined in exponential time. And there exist some languages that can be decided only ...
lz9866's user avatar
  • 305
1 vote
1 answer
45 views

union of NP and co-NP, closure under polynomial time reduction

Is $Union = NP\cup co-NP$ closed under polynomial-time many-one reductions? I understand that in order to be so, for $A\in Union, A \leq_P B $ there should exist a polynomial time computable function $...
obolenskaya00's user avatar
0 votes
1 answer
63 views

Is a problem in NP if it runs in P time on a NDTM, verifiable in P on a DTM, but solution doesn’t halt on a DTM?

Say there was a decision problem which was solved optimally in polynomial time on a non-deterministic Turing machine, and verifiable in polynomial time on a deterministic TM, but would not halt when ...
J Jackson's user avatar

1
2 3 4 5
16