Nested satisfiability

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Nov 1990Embargo end date: 01 Jan 1993 English Publisher:Springer Science and Business Media LLCJournal:Acta Informatica, volume 28, pages 1-6 (issn: 0001-5903, eissn: 1432-0525,

Copyright policy )Funded by:NSF | Analysis of Algorithms

Authors: Donald E. Knuth;

doi: 10.1007/bf02983372 , 10.48550/arxiv.cs/9301111

arXiv: cs/9301111

Nested satisfiability

- Summary
- Subjects
- Metrics

Abstract

A special case of the satisfiability problem, in which the clauses have a hierarchical structure, is shown to be solvable in linear time, assuming that the clauses have been represented in a convenient way.

Related Organizations

Stanford University
United States

Keywords

FOS: Computer and information sciences, Computer Science - Computational Complexity, Computational Complexity (cs.CC)

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	20
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average