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

learn more… | top users | synonyms

-8
votes
0answers
57 views

P=NP and human thought [on hold]

I've been thinking about P=NP a lot, and wonder if there could be a new type of math created - like 23 would equal two plus three, two minus three, two times three, and two divided by three, etc. So ...
1
vote
1answer
20 views

Reduction of 3-SAT to 3-COLOR

The decision version of the 3-COLOR problem is the problem of deciding whether an input graph G(V, E) can be colored using only 3 colors so that no 2 adjacent vertices have the same color. I had ...
0
votes
0answers
19 views

Transportation mininum cost problem

I've got a bit stuck trying to solve the following problem: A number of transport companies each offer various means of transportation, for example company A offers: ...
0
votes
1answer
17 views

Complexity of Subset-Sum when the target sum is a constant

The Subset-Sum decision problem is: Given a set of n non-negative integers S, is there a subset of S that sum to k? If S and k are inputs, the problem is known to be NP-Complete. What about ...
0
votes
0answers
19 views

How can we show that 3-dimensional matching $\le_p$ exact cover?

In exact cover, we're given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise ...
0
votes
1answer
42 views

How do you load $n$ cannisters into $m$ trucks such that no truck is overloaded

We have $n$ cannisters, and for each one there is a specified subset of trucks which can carry it. There are $m$ trucks that can each hold $k$ cannisters. Is there a way to load all $n$ cannisters ...
4
votes
3answers
89 views

Using up letters on a refrigerator is NP-complete

You spend some time with your preschool-age daughter trying to use up all of the magnet letters on the refrigerator to spell words that she knows. Formally, you have a set of letters and you are ...
0
votes
1answer
27 views

Is knowing the size of a minimum vertex cover equivalent to finding a minimal cover?

As most of you know, the problem of finding a minimal vertex cover for an arbitrary graph is an NP-hard problem. I was wondering, if there existed a non-constructive way of calculating the size of a ...
0
votes
1answer
20 views

Proof of why the partition function Z in probabilistic graphical models (PGM) is NP-complete

I was wondering if someone knew why computing the partition function for probabilistic graphical models is NP-Hard? I would like to see a full blown rigorous proof, however, I am as happy to get a ...
0
votes
2answers
64 views

Is there a problem more difficult than NP-complete in graph theory?

There are some decision problems being NP-complete in graph theory, including the problem of deciding if a graph has a hamilton cycle, or determing the chromatic number. Since the number of labeled ...
0
votes
0answers
20 views

Variation of Bin-packing with classes of bins and objects

I'm working on a problem that is a variation of bin-packing, but a bit more general form with extra constraints. The problem definition is as follows- We have objects of varying sizes, which can be ...
0
votes
0answers
33 views

Minimizing sum of weighted product

Consider a total of $d$ items, $\{I_1,I_2, \cdots,I_d\}$, each having a weight $w_i$ (a positive integer), and a total of $m$ bins, $\{B_1,B_2,⋯,B_m\}$. We would like to distribute the items into the ...
0
votes
2answers
30 views

P and NP and NP-complete and NP-hard in simple terms

I'm trying to wrap my head around what all these terms mean and here is my understanding so far. I'm hoping you can improve my understanding of what these terms mean. P is the set of all problems ...
0
votes
1answer
13 views

Non-Deterministic Polynomial Time Algorithm

My understanding is that for problems where there are an exponential number of possible solutions, a non-deterministic turing machine (NTM) is able to solve it in polynomial time because an NTM can ...
0
votes
2answers
63 views

Minimizing sum of products

Consider a total of $d$ items, $\{I_1, I_2, \cdots, I_d \}$, each having a weight $w_i$, and a total of $m$ bins, $\{B_1, B_2, \cdots, B_m\}$. We would like to distribute the items into the bins such ...
1
vote
1answer
49 views

“Job-scheduling” problem that minimizes the number of machines

In a graph, there are points that need to be visited. For each of these points, there is a certain time interval given by its start and ...
0
votes
1answer
24 views

NP-Completeness and NP

Given : $S$ is an $NP-Complete$ problem $Q$ and $R$ are two other problems not known to be in $NP$. $Q$ is polynomial-time reducible to $S$ and $S$ is polynomial-time reducible to $R$. My thoughts ...
2
votes
1answer
50 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 ...
3
votes
3answers
131 views

Minimum vector sets span spaces cover problem

Instance: a set of vectors $V=\{\mathbf{v}_1,\mathbf{v}_2,...,\mathbf{v}_n\}$ and $m$ vector sets $V_1,V_2,...,V_m$, each of which contains multiple vectors ($V_i$ may not be a subset of $V$). In our ...
0
votes
0answers
15 views

Vertex Cover Approximation

Is there any Vertex Cover approximation algorithm that gives the optimal solution for some graphs but otherwise near-optimal solutions for other graphs? Would an algorithm like that be useful? From ...
1
vote
2answers
135 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 ...
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? ...
1
vote
1answer
77 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 ...
2
votes
0answers
29 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
23 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
53 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
130 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
90 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
52 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
31 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
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!
1
vote
1answer
53 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
119 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
29 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
113 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
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 ...
0
votes
3answers
71 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
141 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
731 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
53 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
47 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
52 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
98 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
96 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
71 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 ...