Sets computable in polynomial time on average

DOI10.1007/BFB0030859MaRDI QIDQ6085734zbMATH OpenOpenAlexFDO

Authors Rainer Schuler, Tomoyuki Yamakami

Publication date 12 December 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0030859

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Average polynomial time complexity of some NP-complete problems
• Polynomial-average-time satisfiability problems
• Observations on complete sets between linear time and polynomial time
• scientific article; zbMATH DE number 1072538
• The Pure Literal Rule and Polynomial Average Time
• Some Results on Average-Case Hardness Within the Polynomial Hierarchy
• Some properties of sets tractable under every polynomial-time computable distribution
• On the computational complexity of defining sets
• A theorem on random polynomials and some consequences in average complexity
• scientific article; zbMATH DE number 69493

Cites work

• Almost every set in exponential time is P-bi-immune
• Average Case Complete Problems
• Average case completeness
• Bi-immune sets for complexity classes
• Completeness, Approximation and Density
• Computational complexity of real functions
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• Near-Testable Sets
• On the theory of average case complexity
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Structural average case complexity
• The density and complexity of polynomial cores for intractable sets

This page was built for publication: Sets computable in polynomial time on average

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