A newbie question regarding P
From: Uccai Siravas (uccai_siravas_at_yahoo.com)
Date: 12/08/03
- Next message: David Wagner: "Re: A newbie question regarding P"
- Previous message: Matt Timmermans: "Re: is this hard?"
- Next in thread: David Wagner: "Re: A newbie question regarding P"
- Reply: David Wagner: "Re: A newbie question regarding P"
- Reply: Duke Luke: "Re: A newbie question regarding P"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 7 Dec 2003 21:58:42 -0800
If I understand correctly, every problem in NP can be reduced to SAT
(or any other NP-complete problem) using a polytime reduction.
Is this true of P also? That is, is there a known polytime problem
(call it A) to which each problem in P can be reduced using some
polytime reduction.
An example would be "all problem in P can be reduced to say 2-SAT"
In this case A is 2-SAT.
Are there any (accessible) work done on the characterization of P?
Uccai Siravas
- Next message: David Wagner: "Re: A newbie question regarding P"
- Previous message: Matt Timmermans: "Re: is this hard?"
- Next in thread: David Wagner: "Re: A newbie question regarding P"
- Reply: David Wagner: "Re: A newbie question regarding P"
- Reply: Duke Luke: "Re: A newbie question regarding P"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]