Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EXACT EXPONENTIAL ALGORITHMS:
Reports tagged with exact exponential algorithms:
TR21-112 | 30th July 2021
Vikraman Arvind, Venkatesan Guruswami

CNF Satisfiability in a Subspace and Related Problems

We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace Avoidance (USA) problem), and finding a common zero of a system of ... more >>>




ISSN 1433-8092 | Imprint