Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Philipp Hertel:

TR07-046 | 23rd April 2007
Philipp Hertel

An Exponential Time/Space Speedup For Resolution

Comments: 1

Satisfiability algorithms have become one of the most practical and successful approaches for solving a variety of real-world problems, including hardware verification, experimental design, planning and diagnosis problems. The main reason for the success is due to highly optimized algorithms for SAT based on resolution. The most successful of these ... more >>>

TR07-044 | 23rd April 2007
Philipp Hertel

Black-White Pebbling is PSPACE-Complete

Revisions: 1

The complexity of the Black-White Pebbling Game has remained an open problem for 30 years. It was devised to capture the power of non-deterministic space bounded computation. Since then it has been continuously studied and applied to problems in diverse areas of computer science including VLSI design and more recently ... more >>>

ISSN 1433-8092 | Imprint