meta user
network profile
| bio | website | |
|---|---|---|
| location | ||
| age | 36 | |
| visits | member for | 1 year, 8 months |
| seen | May 9 '12 at 2:58 | |
| stats | profile views | 138 |
|
Sep 2 |
comment |
Oracles and relativization in non-TM settings Going back to the $P?NP$ setting, I don't really have a good understanding of what an $NP^A$-complete problem might look like. Or even if that concept makes sense. For an arbitrary oracle A, is there a nice type of problem such that all problems in $NP^A$ are polynomial-time reducible to a problem of that type? |
|
Sep 2 |
comment |
Oracles and relativization in non-TM settings Okay, thank you! That's very helpful. And I'm not looking at $P?NP$ in a graph theory context necessarily, the second part of my question is if there is some natural way to define a relativized version of a graph theory question -- I didn't think my example was particularly natural. |
|
Sep 1 |
comment |
Is SAT in P^{SAT}? Thank you. So the definition in Wikipedia is flat-out wrong? I have a followup question (related to the non-TM setting version of oracles), but I'll make that separate. |
