scientific article; zbMATH DE number 176526

zbMATH0773.68039MaRDI QIDQ4035692FDOQ4035692

Authors Anne Condon

Publication date 18 May 1993

zbMATH Keywords

NP-completerational seriesinteractive proof systemsprobabilistic finite state automata\(k\)-regular sequencesword problem for matrices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of the max word problem and the power of one-way interactive proof systems
• scientific article; zbMATH DE number 1256636
• The complexity of the word-problem for finite matrix rings
• On the complexity of automatic complexity
• Undecidable problems for probabilistic automata of fixed dimension

Cited in

(7)

• The complexity of approximating a nonlinear program
• Max NP-completeness made easy
• The complexity of computing maximal word functions
• Logspace verifiers, NC, and NP
• The complexity of the max word problem and the power of one-way interactive proof systems
• The Max-Atom Problem and Its Relevance
• On the complexity of partially observed Markov decision processes

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4035692)