Re: Intractability Problem (reduction form 3SAT)
- From: "Radoslaw Hofman" <radekh@xxxxxxxxx>
- Date: Fri, 20 Apr 2007 07:23:18 +0200
Uzytkownik "Ez_Alg" <virtualrealtor@xxxxxxxxx> napisal w wiadomosci
news:1174259673.863479.303370@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
How do we show that if EXPERIMENTAL CUISINE is solvable in polynomial
time, then so is 3SAT.
We cannot because it is not true :)
This problem is solvable in polynomial time - it is simple optimization
problem (see http://en.wikipedia.org/wiki/Linear_Programming)
To create similar NP-hard problem you require additional restrictions - for
example matrix of availability (you have only certain quantity of each
integrate) together with discretion (imagine using packs of integrated, so
if you decide to add A then you have to add 1 pack of A - first would say
that you have only X packs of A available). This one should be harder - you
have to check if it is NP-hard by reduction known NP-complete problem TO it
(consider Knapsack problem).
Remember also that NP-hardness is considered regarding decision problems, so
you have to consider decision problem: for example is there a solution such
that penalty is equal to Y.
Best regards,
Radek Hofman
.
- Prev by Date: Re: more again: the complexity of Hamiltonian problem on 2-regular digraph
- Next by Date: Re: Reducing the Knapsack Problem to the Bin Packing Problem
- Previous by thread: Reducing the Knapsack Problem to the Bin Packing Problem
- Next by thread: hi.....need help in proving this plz.....
- Index(es):
Relevant Pages
|
