Some relationships between logics of programs and complexity theory (Q1106839)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Some relationships between logics of programs and complexity theory |
scientific article |
Statements
Some relationships between logics of programs and complexity theory (English)
0 references
1988
0 references
The authors study some interesting connections between (open) problems in comparative schematology and logics of programs, on one hand, and problems in complexity theory on the other hand. As an example, PSPACE\(=PTIME\) iff flow-diagrams with arrays are of the same computational power as recursive procedures.
0 references
comparative schematology
0 references
PSPACE
0 references
PTIME
0 references
flow-diagrams with arrays
0 references
recursive procedures
0 references
