Robustness of PSPACE-complete sets (Q2379952)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Robustness of PSPACE-complete sets	scientific article

Statements

scholarly article

0 references

Robustness of PSPACE-complete sets (English)

0 references

0 references

0 references

Information Processing Letters

0 references

publication date

24 March 2010

0 references

zbMATH Keywords

computational complexity

0 references

complete sets

0 references

robustness

0 references

P-selective sets

0 references

PSPACE

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.ipl.2007.02.018

0 references

Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)

0 references

Splittings, Robustness, and Structure of Complete Sets

0 references

0 references

PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS

0 references

Properties of NP‐Complete Sets

0 references

Complete sets and closeness to complexity classes

0 references

P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP

0 references

Exponential-time and subexponential-time sets

0 references

On polynomial-time truth-table reducibility of intractable sets to P-selective sets

0 references

Identifiers

zbMATH Open document ID

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

10.1016/J.IPL.2007.02.018

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2379952

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q2379952&oldid=39045363"