Re: Discussion regarding Mr. Diabys algorithm


U¿ytkownik <tchow@xxxxxxxxxxxxx> napisa³ w wiadomo¶ci
news:4564685a$0$578$b45e6eb0@xxxxxxxxxxxxxxxxxxxxxxxxxxxx
In article <1164193065.609496.83820@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Radoslaw Hofman <radekh@xxxxxxxxx> wrote:
For me personally I don't think that UP=NP. We know that UP is in NP
and that UP can express any NP problem... but it does not mean they are
equal.

Careful here...what do you mean by "UP can express any NP problem"?
If there is a UP set that is NP-complete, then UP = NP.

By the way, Lane Hemaspaandra posted a very nice overview of unique
satisfiability questions here some years ago.

http://groups.google.com/group/comp.theory/msg/6d8a3a5edcf4dc29


Thanks for the link - I'll check it soon.

I meant - if one knows way to solve any UP problem in polynomiall time then
he may solve any TSP instance in polynomial time then he can solve any
NP-complete problem in polynomial time then he can solve any NP problem in
polynomial time.

We know that any NP problem may be reduced to SAT, SAT may be reduced to TSP
and TSP to unique version of TSP. That is how UP can express any problem
from NP.

But I think that same as for NP there are two major subclases of UP: UP-P
(unique solution and polynomially solvable) and UP-NP (unique solution
non-polynomialy solvable). We know way to reduce any NP-problem to UP-NP
part. And I think that this Unique TSP is NP-complete, but for me corrolary
UP=NP is not so obvious. Why? Consider 2SAT with many possible solutions -
if we convert it to TSP (we may) we obtain much more hard problem -
converting it to UP (we can as well) shows only that UP can express any NP
problem. We know that UP is subset of NP which can express any NP problem,
but not that it is equal to NP.

Exactly same properties has NP-complete class - it can express any NP
problem and it is subset of NP. But does NP-complete=NP? Noone proved it
yet, and if P!=NP it cannot be proved (same with UP).

Best regards,

Radek Hofman


.

Relevant Pages

  • Re: Consecutive Numbers
    ... NP problem is said to be NP-complete if the>existence of a polynomial ... footing--- if any one of them can be solved in polynomial time, ... to be non-P or NP>"Finding the prime factors of a given integer is ... it does, then factorization, which is certainly in NP ...
    (sci.math)
  • Re: NP-complete and NP-Hard?
    ... > I don't quite understand NP-Complete and NP-Hard problem, ... NP is the class of problems that can be solved in polynomial time (in ... that you need exponential time to solve an NP problem - there might be ...
    (comp.theory)
  • NP-Complete Definition
    ... If B is NP-Complete and B is polynomial-time-reducible to C (where C ... Suppose that the reduction R reduces B to C in polynomial time, ... Maybe the original input to B was of size n, ... The reduction occurs in polynomial time, ...
    (comp.theory)
  • Re: basic query regarding NP Complete...
    ... is a set of NP-Complete problems. ... Forgive me if I sound a little stupid.. ... I suppose cookes ... in NP can be converted in polynomial time into the problem you are claiming ...
    (comp.theory)
Loading