Generic case completeness

DOI10.1016/J.JCSS.2016.05.002MaRDI QIDQ736607zbMATH OpenOpenAlexFDO

Authors Alexander Ushakov, Alexei Myasnikov

Publication date 4 August 2016

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.01172

zbMATH Keywords

completenessgeneric-case complexitybounded halting problemrandomized problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: In this note we introduce a notion of a generically (strongly generically) NP-complete problem and show that the randomized bounded version of the halting problem is strongly generically NP-complete.

Cites work

• scientific article; zbMATH DE number 5982274 (Why is no real title available?)
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 1263208 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• ALMOST EVERY GROUP IS HYPERBOLIC
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Asymptotic density and the Ershov hierarchy
• Average Case Complete Problems
• Average case completeness
• Average-case complexity and decision problems in group theory.
• From bi-immunity to absolute undecidability
• Generic complexity of undecidable problems
• Generic computability, Turing degrees, and asymptotic density
• Generic properties of finitely presented groups and howson's theorem
• Generic-case complexity, decision problems in group theory, and random walks.
• MULTIPLICATIVE MEASURES ON FREE GROUPS
• Nonexistence of minimal pairs for generic computability
• Random walk in random groups.
• Small fast universal Turing machines
• Statistical properties of finitely presented groups
• The halting problem is decidable on a set of asymptotic probability one

Cited in

(1)

• ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY

This page was built for publication: Generic case completeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q736607)