Lowness properties for strong reducibilities and the computational power of maximal sets. (English) Zbl 07832588
MSC:
03Dxx
Found 73 Documents (Results 1–73)
Non-coding enumeration operators. (English) Zbl 07633501
Anselmo, Marcella (ed.) et al., Beyond the horizon of computability. 16th conference on computability in Europe, CiE 2020, Fisciano, Italy, June 29 – July 3, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12098, 112-123 (2020).
MSC:
68Qxx
The robustness of LWPP and WPP, with an application to graph reconstruction. (English) Zbl 1503.68074
Degrees of and lowness for isometric isomorphism. (English) Zbl 1462.03016
Reviewer: Andrei S. Morozov (Novosibirsk)
On low for speed oracles. (English) Zbl 1459.03060
Being low along a sequence and elsewhere. (English) Zbl 1443.03023
Reviewer: Leon Harkleroad (Bowdoinham)
The robustness of LWPP and WPP, with an application to graph reconstruction. (English) Zbl 1512.68103
Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 51, 14 p. (2018).
On low for speed oracles. (English) Zbl 1459.03061
Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 96, Article 15, 13 p. (2018).
Lowness and logical depth. (English) Zbl 1418.03150
Lowness for integer-valued randomness. (English) Zbl 1350.68160
Reviewer: Ludwig Staiger (Halle/Saale)
MSC:
68Q30
Uniform Kurtz randomness. (English) Zbl 1338.03082
MSC:
03D32
Lowness for difference tests. (English) Zbl 1330.03078
Reviewer: Ludwig Staiger (Halle/Saale)
Randomness notions and partial relativization. (English) Zbl 1279.03065
Reviewer: Ludwig Staiger (Halle/Saale)
On the existence of indiscernible trees. (English) Zbl 1279.03062
Reviewer: J. M. Plotkin (East Lansing)
Computably enumerable sets below random sets. (English) Zbl 1314.03040
Reviewer: Vladik Ya. Kreinovich (El Paso)
Lowness notions, measure and domination. (English) Zbl 1262.03068
Reviewer: Noam Greenberg (Wellington)
Studying randomness through computation. (English) Zbl 1250.68135
Zenil, Hector (ed.), Randomness through computation. Some answers, more questions. Hackensack, NJ: World Scientific (ISBN 978-981-4327-74-9/hbk; 978-981-4327-75-6/ebook). 207-222 (2011).
Reviewer: Liang Yu (Nanjing)
Interactions of computability and randomness. (English) Zbl 1258.03053
Bhatia, Rajendra (ed.) et al., Proceedings of the international congress of mathematicians (ICM 2010), Hyderabad, India, August 19–27, 2010. Vol. II: Invited lectures. Hackensack, NJ: World Scientific; New Delhi: Hindustan Book Agency (ISBN 978-981-4324-32-8/hbk; 978-81-85931-08-3/hbk; 978-981-4324-30-4/set; 978-981-4324-35-9/ebook). 30-57 (2011).
Strengthening prompt simplicity. (English) Zbl 1247.03074
MSC:
03D25
Demuth randomness and computational complexity. (English) Zbl 1223.03026
Reviewer: Liang Yu (Nanjing)
Higher Kurtz randomness. (English) Zbl 1223.03025
Relative randomness and cardinality. (English) Zbl 1231.03038
Reviewer: Heribert Vollmer (Hannover)
Lowness and highness properties for randomness notions. (English) Zbl 1193.03072
Arai, T. (ed.) et al., Proceedings of the 10th Asian logic conference, Kobe, Japan, September 1–6, 2008. Hackensack, NJ: World Scientific (ISBN 978-981-4293-01-3/hbk; 978-981-4293-02-0/ebook). 124-151 (2010).
Reviewer: Liang Yu (Nanjing)
Lowness for Kurtz randomness. (English) Zbl 1168.03033
Reviewer: Leon Harkleroad (Wilton)
Computability and randomness. (English) Zbl 1169.03034
Oxford Logic Guides 51. Oxford: Oxford University Press (ISBN 978-0-19-923076-1/hbk). xv, 433 p. (2009).
Reviewer: Cristian S. Calude (Auckland)
Lowness for computable machines. (English) Zbl 1175.03025
Chong, Chitat (ed.) et al., Computational prospects of infinity. Part II: Presented talks. Selected papers of the workshop, June 20–August 15, 2005. Hackensack, NJ: World Scientific (ISBN 978-981-279-654-7/hbk). Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore 15, 79-86 (2008).
Reviewer: Marius Zimand (Towson)
Lowness properties and approximations of the jump. (English) Zbl 1137.03025
Reviewer: Cristian S. Calude (Auckland)
Schnorr trivial reals: a construction. (English) Zbl 1262.03067
Cenzer, D. (ed.) et al., Proceedings of the 3rd international conference on computability and complexity in analysis (CCA 2006), Gainesville, FL, USA, November 1–5, 2006. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 167, 79-93 (2007).
Algorithmic randomness. (English) Zbl 1140.68407
Heidelberg: Univ. Heidelberg, Naturwissenschaftlich-Mathematische Gesamtfakultät. xii, 85 p. (2007).
The complexity of the set of nonrandom numbers. (English) Zbl 1138.03038
Calude, Cristian S. (ed.), Randomness and complexity. From Leibniz to Chaitin. Dedicated to Gregory J. Chaitin on the occasion of his 60th birthday. Hackensack, NJ: World Scientific (ISBN 978-981-277-082-0/hbk). 217-230 (2007).
Reviewer: Cristian S. Calude (Auckland)
Calibrating randomness. (English) Zbl 1113.03037
Reviewer: Cristian S. Calude (Auckland)
Lowness and \(\Pi^0_2\) nullsets. (English) Zbl 1112.03040
Reviewer: Cristian S. Calude (Auckland)
Reals which compute little. (English) Zbl 1107.03047
Chatzidakis, Zoé (ed.) et al., Logic colloquium ’02. Proceedings of the annual European summer meeting of the Association for Symbolic Logic (ASL) and the Colloquium Logicum, Münster, Germany, August 3–11, 2002. Wellesley, MA: A K Peters; Urbana, IL: Association for Symbolic Logic (ASL) (ISBN 1-56881-300-7/hbk; 1-56881-301-5/pbk). Lecture Notes in Logic 27, 261-275 (2006).
MSC:
03D25
Algorithmic randomness and computability. (English) Zbl 1100.68042
Sanz-Solé, Marta (ed.) et al., Proceedings of the international congress of mathematicians (ICM), Madrid, Spain, August 22–30, 2006. Volume II: Invited lectures. Zürich: European Mathematical Society (EMS) (ISBN 978-3-03719-022-7/hbk). 1-26 (2006).
Graph Isomorphism is in SPP. (English) Zbl 1110.68090
On Kurtz randomness. (English) Zbl 1070.68054
Lowness properties of reals and hyper-immunity. (English) Zbl 1264.03093
de Queiroz, Ruy (ed.) et al., Proceedings of the 10th workshop on logic, language, information and computation (WoLLIC’2003), Ouro Preto, Minas Gerais, Brazil, July 29 – August 1, 2003. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 84, 73-79 (2003).
MSC:
03D32
New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. (English) Zbl 1059.68043
MSC:
68Q15
Lectures on complexity theory. (Vorlesungen zur Komplexitätstheorie.) (German) Zbl 0965.68024
Teubner-Texte zur Informatik. 32. Stuttgart: Teubner. 312 S. (2000).
Reviewer: Armin Hemmerling (Greifswald)
On Boolean lowness and Boolean highness. (English) Zbl 0912.68049
Hsu, Wen-Lian (ed.) et al., Computing and combinatorics. 4th annual international conference, COCOON ’98, Taipei, Taiwan, ROC, August 12–14, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1449, 147-156 (1998).
New collapse consequences of NP having small circuits. (English) Zbl 0920.03052
Reviewer: Tao Renji (Beijing)
Nonuniform lowness and strong nonuniform lowness. (English) Zbl 0837.68036
MSC:
68Q15
Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes. (English) Zbl 0733.68031
Reviewer: U.Schöning (Ulm)
MSC:
68Q15
Counting the number of solutions. A survey of recent inclusion results in the area of counting classes. (English) Zbl 0733.68035
Mathematical foundations of computer science, Proc. 15th Symp., MFCS ’90, Banská Bystrica/Czech. 1990, Lect. Notes Comput. Sci. 452, 121-134 (1990).
Robust oracle machines. (English) Zbl 0652.68058
Mathematical foundations of computer science 1988, Proc. 13th Symp., Carlsbad/Czech. 1988, Lect. Notes Comput. Sci. 324, 93-106 (1988).
MSC:
68Q25
68Q05
Graph isomorphism is in the low hierarchy. (English) Zbl 0621.68034
STACS 87, Theoretical aspects of computer science, Proc. 4th annu. Symp., Passau/FRG 1987, Lect. Notes Comput. Sci. 247, 114-124 (1987).
Variations on promptly simple sets. (English) Zbl 0589.03025
Reviewer: C.Calude
MSC:
03D25
Sparse oracles, lowness, and highness. (English) Zbl 0554.68033
Mathematical foundations of computer science, Proc. 11th Symp., Praha/Czech. 1984, Lect. Notes Comput. Sci. 176, 185-193 (1984).
Information content characterizations of complexity theoretic properties. (English) Zbl 0401.68022
Theor. Comput. Sci., 4th GI Conf., Aachen, 1979. Lect. Notes Comput. Sci. 67, 58-66 (1979).
Filter Results by …
Document Type
- Journal Articles (52)
- Collection Articles (18)
- Books (3)
all
top 5
Author
- Nies, André Otfrid (17)
- Downey, Rodney Graham (11)
- Miller, Joseph S. (6)
- Ng, KengMeng (6)
- Franklin, Johanna N. Y. (5)
- Watanabe, Osamu (5)
- Bienvenu, Laurent (4)
- Miyabe, Kenshi (4)
- Schöning, Uwe (4)
- Stephan, Frank (4)
- Yu, Liang (4)
- Barmpalias, George (3)
- Book, Ronald Vernon (3)
- Diamondstone, David E. (3)
- Greenberg, Noam (3)
- Hemaspaandra, Lane A. (3)
- Kjos-Hanssen, Bjørn (3)
- Arvind, Vikraman (2)
- Bennison, Victor L. (2)
- Figueira, Santiago (2)
- Hemaspaandra, Edith (2)
- Hirschfeldt, Denis Roman (2)
- Kihara, Takayuki (2)
- Köbler, Johannes (2)
- Mihailović, Nenad (2)
- Reith, Steffen (2)
- Spakowski, Holger (2)
- Turetsky, Dan (2)
- Wagner, Klaus W. (2)
- Weber, Rebecca (2)
- Ambos-Spies, Klaus (1)
- Balcázar, José Luis (1)
- Balćzar, José L. (1)
- Bedregal, Benjamín René Callejas (1)
- Brattka, Vasco (1)
- Cai, Jin-Yi (1)
- Chakaravarthy, Venkatesan T. (1)
- Chong, Chi Tat (1)
- Epstein, Rachel (1)
- Griffiths, Evan J. (1)
- Herbert, Ian (1)
- Kämper, Jürgen (1)
- Ko, Ker-I (1)
- Kučera, Antonín (1)
- Kurur, Piyush P. (1)
- Lempp, Steffen (1)
- Li, Guanying (1)
- Li, Hongzhou (1)
- Maass, Wolfgang (1)
- McInerney, Michael (1)
- McNicholl, Timothy H. (1)
- Merkle, Wolfgang (1)
- Miller, Russell G. (1)
- Monath, Martin (1)
- Ogihara, Mitsunori (1)
- Orponen, Pekka (1)
- Reid, Stephanie (1)
- Russo, David A. (1)
- Soare, Robert I. (1)
- Solomon, Reed (1)
- Takeuchi, Kota (1)
- Terwijn, Sebastiaan A. (1)
- Torán, Jacobo (1)
- Tsuboi, Akito (1)
- Turetsky, Daniel D. (1)
- Wechsung, Gerd (1)
- Yanagimoto, Takemi (1)
all
top 5
Serial
- J. Symb. Log. (8)
- Ann. Pure Appl. Logic (8)
- Theor. Comput. Sci. (5)
- SIAM J. Comput. (4)
- J. Comput. Syst. Sci. (3)
- J. Log. Comput. (3)
- Computability (3)
- Notre Dame J. Formal Logic (2)
- Inf. Comput. (2)
- Inf. Process. Lett. (1)
- Isr. J. Math. (1)
- J. Lond. Math. Soc., II. Ser. (1)
- Proc. Lond. Math. Soc. (3) (1)
- Stat. Probab. Lett. (1)
- J. Comput. Sci. Technol. (1)
- Arch. Math. Logic (1)
- Comput. Complexity (1)
- Math. Log. Q. (1)
- Bull. Symb. Log. (1)
- Theory Comput. Syst. (1)
- J. Math. Log. (1)
- Oxf. Logic Guides (1)
- Teubner-Texte Inform. (1)
- Log. Methods Comput. Sci. (1)
- J. Log. Anal. (1)
