Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science

learn more… | top users | synonyms

0
votes
1answer
62 views

P, NP-Complete and NP-Hard Problems

I have confusion over P, NP-Complete and NP-Hard problems. I understand a polynomial time algorithm is one which can be solved for a an input string of length n. But why would a problem not be in ...
0
votes
1answer
27 views

Prove language is in $NP$ without using a reduction

I've been stuck on this question for hours, can't seem to figure this out. $L = \{\langle M, x, y \rangle\ |\ M$ is a non-deterministic Turing machine over $\{0,1\}$ and $x,y \in \{0,1\}^*$ and ...
0
votes
2answers
35 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): ...
2
votes
1answer
59 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 ...
0
votes
0answers
24 views

Proof: $\alpha \mid p_j=1,r \mid \gamma$ is at least as easy as $\alpha \mid r_j, pmtn \mid \gamma$

I have to prove the following: show that the problem $\alpha \mid p_j=1,r_j \mid \gamma$ is at least as easy as the problem $\alpha \mid r_j, pmtn \mid \gamma$ if all processing times and release ...
0
votes
3answers
64 views

Gaining Mid-level Understanding of P vs NP

I have a base understanding of N and NP, but I want to find some material to gain a better understanding to it. E.g. 'Mid-level', something that goes more into depth of it. Any suggestions for PhD ...
0
votes
1answer
118 views

Chaos Theory and Sum Subset Problem

In respect to the "P versus NP" controversy, can't chaos theory be used to solve problems like the Sum Subset Problem with non exponential performance? Like, chaotic equations, are like paths to very ...
5
votes
1answer
639 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 ...
0
votes
0answers
14 views

In the definition of NP, is it required to have polynomially bounded length of certificate?

So given the definition in our lectures, we were told that NP is defined as the set of languages $L$ s.t. there exist a polynomial time bounded Turing-acceptor M s.t. $L ={w: M accepts(w#c) for some ...
0
votes
1answer
37 views

Optimization problem for feeding the hungry

So I am trying to solve a problem. I believe it is $NP$. Assume we have $F$ cans of food of varying sizes. There are $P$ homeless people at the local shelter, where $F>P$. Each can of food, $i$ , ...
0
votes
0answers
40 views

Proof for ACYCLIC PARTITION being an NP-complete problem

I'm new to this site, so please pardon me for any mistakes and please feel free to edit the question to help get better answers. I'm interested in reading any proof of ACYCLIC PARTITION (Garey and ...
0
votes
0answers
47 views

What is an algebraic expression over a field structure?

I am working on a problem, and I am not understanding the language very well. Here is the setup of the problem: Consider the set $\{ 0, 1, 2 \}$ with the operations addition $(+)$ modulo $3$ and ...
1
vote
2answers
84 views

Which pure mathematical problems could be tackled with an algorithm solving NP-complete problems?

In the past, practical applications have motivated the development of mathematical theories, which then became the subject of study in pure mathematics, where mathematics is developed primarily for ...
0
votes
0answers
35 views

path of length >=k in polytime in bipartite graph

I am trying to find whether it is possible to find a path of length greater than or equal to k, given the starting and ending vertices, in a bipartite in polynomial time, or whether this is NP-hard. ...
0
votes
0answers
14 views

How do I reduce 3-SAT to a 3-SAT NAE problem?

I am trying to figure out how to reduce a 3SAT problem to a 3SAT NAE (Not All Equal) problem. Not only that, I also figure out that I am not so sure about the reduction to 3SAT either. Anyway, how ...
2
votes
1answer
24 views

NP question - how to reduce this Graph problem?

I am losing my head on Algorithms (namely P-NP stuff) and I thought I would pop over here. I have a question: in my last exam (which went rather bad :/ ) there was a question which was on the line ...
0
votes
1answer
21 views

seat every club member np problem

A University has n clubs, the largest of which contains m members (students can be members of multiple clubs). The President of the University wishes to hold a dinner in honor of such student ...
2
votes
2answers
56 views

np or np complete proof of a factory problem

Good evening everyone; I face with this problem and I could not find a way to proof it. Here is the problem; A={Writing out the factorial of a number in unary NP-complete or NP-hard (e.g. n! = 11 ...
0
votes
1answer
30 views

should we try to solve problem in np class

Good afternoon everyone; I am having difficulties to discriminate between NP and NP completeness. For instance, we know that a problem is in NP class should we try to find a algorithmic solution for ...
1
vote
0answers
34 views

Is Quadratically Constrained Quadratic Program (QCQP) in NP?

The general version of QCQP is NP-hard, but is it also NP-complete? That means, is there a non-deterministic algorithm, which solves QCQP in polynomial time complexity? If the general version of QCQP ...
2
votes
2answers
60 views

Minimum number of elements needed from n sets

Suppose that we have n sets. They may or may not have common elements. How can we find the minimum number of elements that we should pick so that we have at least one element from each set? For ...
0
votes
0answers
49 views

Proof of: if L is NP-Complete then its complement is coNP-Complete

I have trouble understanding why we need to construct a function to do the following proof and how the function shows that $A \leq_{p} L$: Claim: If L $\epsilon$ NP then $\overline{L}$ is ...
7
votes
1answer
122 views

Is it possible that P != NP cannot be proved?

I am probably asking a stupid question but what I gather from a layman explanation of Godel's incompleteness theorem is that it is completely possible that a true statement cannot be derived from ...
2
votes
1answer
91 views

Finding no-self-intersecting path in geometric graphs

Is there a polynomial algorithm to determine whether there exists no-self-intersecting path between given vertices $s$ and $t$ in a geometric graph $G$? Geometric graph is an image of a graph on a ...
5
votes
2answers
184 views

NP-complete: One proof to rule them all

To prove a decision problem $C$ is in NP-complete, 2 things need to be shown: There is a polynomial verification for $C$ solution. Every problem in NP is reducible to $C$ - You can solve all the ...
5
votes
5answers
439 views

How to prove that $P \neq NP$

How to prove that $P \neq NP$? To prove that $P = NP$ all we need to do is to solve one NP-Complete problem in polynomial time for any input, and because all the NP-Complete problems have reduction ...
1
vote
0answers
71 views

How to prove the NP-hardness of this scheduling problem

Suppose there are a set of $m$ jobs $J= \{J_1, J_2, \ldots, J_m\}$ and $n$ machines $M=\{M_1, M_2, \ldots, M_n\}$. Each job $J_i$ consists of $k_i$ unit operations, and there are totally K operations ...
0
votes
2answers
213 views

What is wrong with this proof: P = NP using polynomial solution for UHP

I am going to show you a proof for P=NP, please tell me where I am wrong. Working space: Symmetric(the distance from AB is equal to BA) Graph with N nodes and M edges. Goal: find a Hamilton path. ...
0
votes
1answer
49 views

Algorithm for valid 3 coloring.

If we have P=NP, how can I show that a polynomial algorithm exists that given any 3 colourable graph produces a valid 3 colouring (no two adjacent vertices share the same colour)?
1
vote
2answers
50 views

Why do Integer Relation Algorithms (e.g. PSLQ) not solve the knapsack problem?

I'm trying to understand what mistake I'm making or what incorrect information I fail to recognize as such. The subset sum problem (given distinct $a_i$ and $A$, does any subset of ${ a_i }$ sum to ...
1
vote
2answers
125 views

Why is the decision problem of the “Travelling Salesman” $\in \mathcal{NP}$?

One of the most well-known problems that belongs into the class of $\mathcal{NP}$-complete problems is the Travelling Salesman Problem. However, I fail to see why it is "so obviously" in ...
0
votes
1answer
55 views

DNF-Equivalence Problem

I have the following Equivalent DNF problem: Input:Two DNF formulas, $F_1$ and $F_2$,with variables $a_1,a_2,...a_n.$ Output: $1$ if $F_1$ and $F_2$ are equivalent, $0$ otherwise. $F_1$ and $F_2$ ...
1
vote
1answer
98 views

How to prove the NP-hardness of this modified set covering problem

In the Set Covering problem, we are given a ground set $U$ and a collection $S$ of subsets of $U$, where each subset is associated with a non-negative cost, the Set Cover problem asks to find a ...
1
vote
1answer
32 views

Does the way a graph $G$ is encoded affect the proof that $CLIQUE$ is in $NP$?

For a proof that $CLIQUE = \{ \langle G, k \rangle | G$ is an undirected graph with a $k$-clique. $\}$ is in $NP$ by constructing a nondeterministic Turing machine $N$, where $N$ = $``$On input ...
3
votes
2answers
162 views

Simple problem whose approximation ratio is still open.

I am preparing for a talk on "Approximation Algorithms", aimed at undergraduate students. In order to motivate the topic, I want to give them an example of a problem which is easy to describe and has ...
-3
votes
1answer
387 views

Is solving the PvsNP example question a solution to PvsNP?

This example question was created by the claymath institute. The PvsNP question states, suppose the dean leaves you with a task to house a group of 400 students inside dorms. But there is only enough ...
0
votes
1answer
36 views

Fastest path to cover area

How do we determine the fastest path to cover an area using an object of some radius r? E.g. a machine that needs to spray a chemical onto a surface. I assume this is some kind of NP-hard problem.
-4
votes
1answer
182 views

How does 3-sat work in laymen's terms?

I know only basic math like so: (+,-,x,\,). And I studied a little bit of programming up to the point of knowing a little bit about Boolean values.I desperately want to understand the 3-sat question ...
0
votes
0answers
58 views

Please explain the unsolved 3-sat math problem as easy as possible for someone with only basic math skills [duplicate]

I know only basic math like so: (+,-,x,\,). And I know a little bit of programming up to the point of Boolean values.I desperately want to understand the 3-sat question fully so I can solve it, but ...
1
vote
1answer
104 views

Is this problem NP-complete?

Let matrix $M \in \{0,1\}^{r \times (c+1)r}$ for some $c \in \Bbb Z_{+}$ be given. Is it NP-complete to decide if $\exists u \in \{0,1\}^{1 \times r}$ $:$$\prod_i v_i \in 2\Bbb Z+1$ where $v=uM$?
1
vote
1answer
119 views

Simon's algorithm for n = 3

The Simon's problem is as follows: Suppose we are given a function $f : \{0, 1\}^n \to \{0, 1\}^m$, with $m \ge n$, and we are promised that either $f$ is 1-to-1, or there exists a non-trivial s such ...
0
votes
1answer
29 views

Minimizing an unknown system's output

Let we have an unknown system with two inputs and two outputs. inputs $x=[x_1 x_2]$ and outputs $y=[y_1 y_2 ]$ The system have the following properties $ y_1 = f_1(x_1,x_2)$ ; $y_2 = f_2(x_1,x_2) $ ...
1
vote
0answers
32 views

Highest known minimum bipartite crossing number?

I'd like to know what the highest known complete bipartite minimum crossing number graph K is? Last I knew it was K 7,7 , has K 8,8 been conjectured or proven yet? Any info on where I could find ...
0
votes
2answers
79 views

non-Hamiltonian Cycles: How to Prove for Small Graphs

How do I prove that the following graph is a non-Hamiltonian cycle? $\hspace{5.3cm}$ I'm asked to create a graph which is both non-Eulerian and non-Hamiltonian, and this is what I produced in TiKz. ...
1
vote
1answer
143 views

I don't understand the proof for reducing Subset-Sum to Scheduling with release time.

I found this proof for showing that Scheduling with Release Time is NP-Hard by reduction to Subset-sum, but I don't understand it: Scheduling With Release Time: Given a set of $n$ jobs with ...
1
vote
2answers
623 views

is the Sudoku puzzle NP-complete?

In general Sudoku on $n^2 \times n^2$ boards of $n \times n$ blocks is NP-complete. Is the common Sudoku on $9 \times 9$ board NP-complete?
0
votes
0answers
63 views

Solving a system of multivariate (possibly homogeneous) polynomials over $\mathbb{Q}_p$ efficiently

after an unsuccessful search for appropriate literature, I thought to post my question here: Suppose a system $F$ of $n$ polynomials in $n+1$ variables having coefficients in $\mathbb{Q}_p$: ...
0
votes
0answers
87 views

How to prove that a decision problem belongs to PSPACE?

Prove that QBF, defined below, belongs to PSPACE. QBF Input: a quantified Boolean formula $$F = (Q_1x_1)(Q_2x_2) · · · (Q_nx_n)B(x_1, . . . , x_n)$$ where $B(x_1, . . . , x_n)$ is a ...
1
vote
1answer
105 views

Characterization of Subset Sum via Linear Programming

I have a sample subset sum problem. Given numbers $x_1, x_2... x_N$ and a target value to sum to $x_S$ Minimize $x_S - x_1y_1 - x_2y_2 - x_3y_3 ... x_Ny_N$ such that 0 <= $y_1$ <= 1 0 <= ...
0
votes
0answers
75 views

Hamiltonian cycle problem: how to prove NP-completeness?

How to prove that finding a Hamiltonian cycle in a graph is an NP-complete problem? Should I try to reduce the travelling salesman problem (TSP) to this one (Hamiltonian cycle)?