Monadic logical definability of NP-complete problems

1995 
It is well known that monadic second-order logic with linear order captures exactly regular languages. On the other hand, if addition is allowed, then J.F.Lynch has proved that existential monadic secondorder logic captures at least all the languages in NTIME(n), and then expresses some NP-complete languages (e.g. knapsack problem).
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    0
    References
    5
    Citations
    NaN
    KQI
    []