Packet 12: Tossup 17
Minimizing a model named for having this property is done with the Kameda–Weiner algorithm. Angelic and demonic variants of this property are used for analysis of termination. Any problem solvable in space f-of-n with this property can be solved without this property in space at most f-of-n squared by Savitch’s theorem. An n-state model with this property is converted into a 2-to-the-n state model without this property with an algorithm that includes a step of removing epsilon transitions, the (*) powerset construction. Pushdown automata with this property recognize context-free languages. If a Turing machine with this property can solve a problem in polynomial time, a Turing machine without this property can verify a solution in polynomial time. For 10 points, what does the “N” stand for in the NP complexity class? ■END■
ANSWER: nondeterminism [or word forms like nondeterministic; accept nondeterministic finite automaton or nondeterministic polynomial time; prompt on NSPACE or NPSPACE; prompt on NFA; prompt on NP; prompt on finite until “Savitch” with “what other property do those models have?”]
<KY, Other Science (Computer Science)> | NAFTA-Packet-12
= Average correct buzzpoint
Back to tossups