Do you want BuboFlash to help you learning these things? Or do you want to add or correct something? Click here to log in or create user.

#computation #social-choice

1 .5 basic concepts in theoretical computer science 19 C , we denote by C C the set of all problems that can be solved by an algorithm for C equipped with C -oracles, where a C -oracle solves a problem in C (or in coC ) in unit time. The class P 2 , defined as P NP , is thus the class of all decision problems that can be solved in polynomial time with the help of NP-oracles, which answer in unit time whether a given instance of a problem in NP is positive or not. The class P 2 is the subset of P 2 consisting of all decision problems that can be solved in polynomial time using “logarithmically many” NP-oracles. Equivalently, P 2 may be defined as the subset of P 2 for which a polynomial number of NP-oracles may be used, but these need to be queried in parallel, that is, we cannot use the answer to one oracle to determine what question to put to the next oracle. Finally, P 2 = NP NP and P 2 = co NP 2 . Thus, for instance, P 2 is the class of decision problems for which the correctness of a positive solution can be verified in polynomial time by an algorithm that has access to an NP-oracle. The following inclusions hold: P ⊆ NP, coNP ⊆ P 2 ⊆ P 2 ⊆ P 2 , P 2 . It is strongly believed that all these inclusions are strict, although none of them was actually proven to be strict. Interestingly, P 2 and (to a lesser extent) P 2 , P 2 and P 2 play an important role in computational social choice (and indeed, we find them referred to in Chapters 3, 4, 5, 8, 12, and 17). We occasionally refer to other complexity classes (such as PLS or #P) in the book; they are introduced in the chapter concerned. For a full introduction and an extensive overview of computational complexity theory, we refer the reader to Papadimitriou (1994) and Ausiello et al. (1999).

If you want to change selection, open document below and click on "Move attachment"

status | not read | reprioritisations | ||
---|---|---|---|---|

last reprioritisation on | suggested re-reading day | |||

started reading on | finished reading on |

Do you want to join discussion? Click here to log in or create user.