scientific article; zbMATH DE number 15884

MaRDI QIDQ3972530zbMATH OpenFDO

Authors Martín Abadi, Andrei Broder, Joan Feigenbaum, Lane A. Hemaspaandra, Eric Allender

Publication date 25 June 1992

zbMATH Keywords

SAToracleNPcryptographically secure one-way functionsinvulnerable generatorstest data for heuristic algorithmszero- knowledge proof systems

Mathematics Subject Classification ID

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

Recommendations

• Generating hard satisfiability problems
• On generating all solutions of generalized satisfiability problems
• scientific article; zbMATH DE number 2196508
• Generating instances for MAX2SAT with optimal solutions
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Generating and measuring instances of hard semidefinite programs
• An algorithm for the automatic solution of constructive problems

Cited in

(9)

• Generating applicable synthetic instances for branch problems
• Practical proofs of knowledge without relying on theoretical proofs of membership on languages
• On separating proofs of knowledge from proofs of membership of languages and its application to secure identification schemes
• On the effective generation of set elements within specified ranges
• On sets polynomially enumerable by iteration
• Uniform generation of NP-witnesses using an NP-oracle
• On the complexity of test case generation for NP-hard problems
• On the complexity of ranking
• On the theory of average case complexity

This page was built for publication:

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