User:Wim van Dam

From Wikipedia, the free encyclopedia

You have new messages (last change).

[edit] About this page

This is my personal page, which I will use mostly as a sandbox. To get some proper information about me, go to my home page at UC Santa Barbara. This is very much my sandbox.

[edit] Sandbox on Reductions in Complexity Theory

In complexity theory reductions between problems play an important role, as they allow us talk about the relative hardness of problems. When there is a reduction from A to B such that B is at least as hard as A, we denote this by a no greater than symbol between A and B with a subscript indicating the specific reduction that is used. Here are the three most relevant ones.

  • A\leq_T B Turing or Cook reduction, if there exists a polytime deterministic algorithm that decides for each possible x whether or not x\in A using queries to an oracle for the problem B.
  • A \leq_{tt} B truth table reduction if there exist a polytime deterministic algorithm that decides membership of A using non-adaptive queries to the oracle for B.
  • A \leq B or A \leq_m B Karp or many one reduction, if there exists a polytime computable function F such that for all x it holds that x \in A if and only if F(x)\in B.

Some examples of the difference between these reductions are:

  • Although the traveling salesman problem sits in \mathsf{NP}, finding the exact length has to be done adaptively (most likely), hence random decision problems about the shortest length does not sit in \mathsf{NP}, although it Turing reduces to it, hence such problems sit in in the complexity class \Delta_2^p = \mathsf{P}^{\mathsf{NP}} := \{ L : L \leq_T \mathrm{SAT}\}.

In general \mathsf{P}^B := \{A : A \leq_T B\}.

  • Consider the decision problem "Given two Boolean formulas, determine whether or not exactly one of them is satisfiable." This requires two non-adaptive queries, hence this problem sits in \Theta_2^p = \mathsf{P}^{\mathsf{NP}}_{\|} := \{ L : L \leq_{tt} \mathrm{SAT}\}, but it does not sit in \mathsf{NP} or in \mathsf{co}-\mathsf{NP} as far as we know (the \| indicates the pararallelness of the queries).
  • The fact that SAT is \mathsf{NP}-complete means that for all A\in \mathsf{NP} we have A\leq \mathrm{SAT}.
Retrieved from "http://en.wikipedia.org../../../w/i/m/User%7EWim_van_Dam_1a55.html"