×

Found 17 Documents (Results 1–17)

All superlinear inverse schemes are coNP-hard. (English) Zbl 1096.68064

Fiala, Jiří(ed.) et al., Mathematical foundations of computer Science 2004. 29th international symposium, MFCS 2004, Prague, Czech Republic, August 22–27, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22823-3/pbk). Lecture Notes in Computer Science 3153, 368-379 (2004).
MSC:  68Q17 68Q15
PDFBibTeX XMLCite
Full Text: DOI

P-immune sets with holes lack self-reducibility properties. (English) Zbl 0983.68077

Calude, C. S. (ed.) et al., Combinatorics, computability and logic. Proceedings of the 3rd international conference, DMTCS ’01. The conference was dedicated to Prof. Frank Harary on the occasion of the 80th birthday. Univ. of Auckland, New Zealand and Univ. of Constanţa, Romania, 2001. London: Springer. Discrete Mathematics and Theoretical Computer Science. 115-124 (2001).
MSC:  68Q15
PDFBibTeX XMLCite

Extending downward collapse from 1-versus-2 queries to \(j\)-versus-\(j+1\) queries. (English) Zbl 0936.68048

Meinel, Christoph (ed.) et al., STACS 99. 16th annual symposium on theoretical aspects of computer science, Trier, Germany, March 4-6, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1563, 270-280 (1999).
MSC:  68Q15
PDFBibTeX XMLCite

Query order in the polynomial hierarchy. (English) Zbl 1507.68122

Chlebus, Bogdan S. (ed.) et al., Fundamentals of computation theory. 11th international symposium, FCT ’97, Jagiellonian Univ., Kraków, Poland, September 1–3, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1279, 222-232 (1997).
MSC:  68Q15
PDFBibTeX XMLCite
Full Text: DOI

A downward translation in the polynomial hierarchy. (English) Zbl 1498.68115

Reischuk, Rüdiger (ed.) et al., STACS 97. 14th annual symposium on theoretical aspects of computer science. Lübeck, Germany, February 27 – March 1, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1200, 319-328 (1997).
MSC:  68Q15
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Year of Publication

Main Field