cnf/dnf approximation

From: V.Z.Nuri (vznuri_at_yahoo.com)
Date: 10/12/04

  • Next message: V.Z.Nuri: "**theory-edge** mailing list" 
    Date: 11 Oct 2004 20:21:57 -0700

    hi all, the following problem arose in my
    study of complexity theory & I wonder if anyone
    would have some insight. I suspect this is a
    deep question that may have many ties to diverse
    areas of theory.

    consider monotone CNFs/DNFs. define a k-width CNF
    as a CNF with all clauses having a max of k literals.

    question: given a k-width CNF "f", find a k-1
    width CNF f' that minimizes the number of "errors".
    the k-1 width function f' is called the "approximation"
    of "f".

    "error" is defined in the obvious way: sum
    of "false positives" plus "false negatives" when
    f' is used as the "approximation" of "f". (there are
    2^n possible "samples", all either corect or false positive
    or false negative, where 'n' is number of input
    bits.)

    so far, I find it difficult to prove anything at
    all about the form of f' despite my suspicion
    that there must be some straightfwd properties.

    the problem can also be seen as a compression algorithm.
    the k-width formula specifies a function and the
    k-1 width formula is a lossy compression in at least
    one sense, that it is not exact. (however I dont know
    if f' would actually require more or less "information"
    than f, although some experiments seem to suggest less).

    I have attacked this problem empirically using
    different techniques, including
    bayardo's relsat program. I have shown that at least
    for some "f", it is not the case that the optimal
    approximation has only clauses that are k-1 width
    subsets of the "f" clauses. Ive also done some work
    with a genetic algorithm to find the minimum for
    given functions.

    I have found vaguely similar investigations by
    cadoli (building on a paper by pippenger)
    & jukna in the literature which I outline in
    this msg. these are the closest Ive found.

    http://groups.yahoo.com/group/theory-edge/message/10154

    I also think that hamming codes might have
    some kind of relationship to the problem, although
    I havent nailed this down yet.

    from my own investigation,
    the problem is particularly relevant for specific
    functions f, such as an NP complete function like
    "clique".

    I ran into it investigating lower bounds
    proofs but it seems to have a theoretical
    independence from them. ie interesting to study
    in its own right. fundamental.

    any feedback appreciated
    thanks

  • Next message: V.Z.Nuri: "**theory-edge** mailing list"
    • Quantcast