scientific article; zbMATH DE number 176526

zbMATH Open0773.68039MaRDI QIDQ4035692FDOQ4035692

Authors: Anne Condon 

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

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

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)

Cited In (7)

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

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)