Some relationships between logics of programs and complexity theory (Q1106839)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4063081
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Some relationships between logics of programs and complexity theory |
scientific article; zbMATH DE number 4063081 |
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
0.8126609325408936
0 references
0.7791474461555481
0 references
0.7647748589515686
0 references
0.7503142356872559
0 references
