learning k-term DNF and k-CNF

From: Sicco Verwer (sicco_at_ik)
Date: 02/25/05

  • Next message: JXStern: "Re: Cerberus and Quine" 
    Date: Fri, 25 Feb 2005 14:08:17 +0100

    Hi,

    I need help understanding a principle in computational learning theory.
    Basically what I do not understand is this:

    learning 3-term DNF is NP-complete
    learning 3-CNF is efficiently PAC learnable (is RP)

    I can solve 3-term DNF by solving it in 3-CNF space, this is efficient
    (RP). There is a polynomial transformation from 3-term DNF to an
    equivalent 3-CNF formula.

    How come this does not imply RP = NP? Am I missing some exponential
    factor somewhere or is the 3-CNF solution not a real solution for the
    3-term DNF problem? Why can't I solve for example 3 graph coloring,
    which is reducible to learning 3-term DNF formulas, by learning CNF
    formulas?

    thanks,
    Sicco Verwer

  • Next message: JXStern: "Re: Cerberus and Quine"