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

learn more… | top users | synonyms

15
votes
1answer
2k views

Why are there only a few known Ramsey numbers?

Can someone explain in a simple way, why there are so few known exact Ramsey Numbers? I guess it's because there are no efficient algorithms for this task, but are there so many combinations to test? ...
0
votes
0answers
19 views

The problem category of sudoku Puzzle solved by search algorithms

Good day everybody, Sudoku puzzle solvers have been categorized in the literature to: Deductive algorithms that perceive sudoku as a hard constraint satisfaction problem (CSP) or Boolean ...
-1
votes
1answer
47 views

NP vs CO vs P Problem

if we assume set of all tautology in predicate logic, with above assumption is : 1) NP Complete? 2) NP but not NP- Complete? 3) CO-NP Complete? 4? CO-NP but not CO-NP Complete? i ran into a ...
1
vote
1answer
44 views

Prove that the “even” subset sum problem is NP-complete

I need to prove that the even subset sum problem is NP-complete. "Given a finite set of natural numbers and an even number $n$, decide whether a subset of the given set exists such that the ...
1
vote
0answers
21 views

Decidability of $P = NP$?

(Please, don't sign this as duplicate of this question, they are not.) Is it possible, that the well-known $P=NP$ conjecture is undecidable in ZFC? Is there any result about this topic?
1
vote
1answer
18 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?
1
vote
0answers
51 views

Math Symbols for “Must be Finite”

I want to express the following two sentences in mathematical syntax (if possible): The number of solutions to the problem should be finite and each solution should be of polynomial length More ...
3
votes
2answers
99 views

Proof that SAT is NPC

I am not really sure I understand the idea behind Cook theorem (it says that SAT is a NP-complete problem). I read the proof with all its parts corresponding to the Turing machine TM solving it (TM ...
1
vote
1answer
72 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, ...
1
vote
1answer
46 views

Existence of a trail of given length in a graph - NPC?

I am trying to determine, whether the problem of a trail of given length in a graph is a NPC problem. We have a graph $G = (V, E)$ and $k \in N^+$. Does this graph contain a trail of length at least ...
0
votes
0answers
26 views

Independent Sets that are Odd Covers

I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd ...
1
vote
1answer
25 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!
1
vote
1answer
43 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? ...
0
votes
1answer
90 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
28 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
56 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
62 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
68 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
131 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 ...
6
votes
1answer
678 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
41 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
43 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
51 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
92 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
36 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
43 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
63 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
31 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
39 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
67 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
1answer
120 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 ...
10
votes
1answer
166 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
107 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
202 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
486 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
77 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
219 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
62 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
76 views

Why do Integer Relation Algorithms (e.g. PSLQ) not solve the subset sum 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
142 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
62 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
106 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
43 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
169 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
417 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
39 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.