scientific article; zbMATH DE number 3566230
From MaRDI portal
zbMath0363.68125MaRDI QIDQ4138187
Publication date: 1975
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Complexity of a class of nonlinear combinatorial problems related to their linear counterparts, A lower bound for tree resolution, Easy problems are sometimes hard, Unique satisfiability of Horn sets can be solved in nearly linear time, A new algorithm for the propositional satisfiability problem, On edge transitivity of directed graphs, New local search approximation techniques for maximum generalized satisfiability problems, The computational complexity of probabilistic inference using Bayesian belief networks, A computationally intractable problem on simplicial complexes, On the lattices of NP-subspaces of a polynomial time vector space over a finite field, Unit disk graph recognition is NP-hard, Complexity of tile rotation problems, On certain polytopes associated with graphs, A hierarchy for nondeterministic time complexity, Non-Horn clause logic programming, Parallelizing SMT solving: lazy decomposition and conciliation, Counting the number of solutions for instances of satisfiability, On the complexity of string folding, Deterministic job-shop scheduling: Past, present and future, Binary interactions and subset choice, Resolution deduction to detect satisfiability for another class including non-Horn sentences in propositional logic, Bandwidth contrained NP-complete problems, Linear programs for constraint satisfaction problems, On the r,s-SAT satisfiability problem and a conjecture of Tovey, The complexity of the word problems for commutative semigroups and polynomial ideals, Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem, Fast algorithms for bin packing, Parallel beta reduction is not elementary recursive, Tractable reasoning via approximation, Typical case complexity of satisfiability algorithms and the threshold phenomenon, Backtracking tactics in the backtrack method for SAT, Solving satisfiability in less than \(2^ n\) steps, Complete divisibility problems for slowly utilized oracles, On the construction of parallel computers from various basis of Boolean functions, The principle of optimality in the design of efficient algorithms, On universal learning algorithms, The NPO-completeness of the longest Hamiltonian cycle problem, A linear-time transformation of linear inequalities into conjunctive normal form, Complexity versus stability for classes of propositional formulas, Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems, The Helly property on subfamilies of limited size, Constrained multi-object auctions and \(b\)-matching, NP is as easy as detecting unique solutions, Scheduling with semaphore constraints, One-way functions and circuit complexity, A note on complete problems for complexity classes, Some results and experiments in programming techniques for propositional logic, A parallel approach for theorem proving in propositional logic, Checking local optimality in constrained quadratic programming is NP- hard, A computational model for RNA multiple structural alignment, Quantum cooperative search algorithm for 3-sat, A competitive and cooperative approach to propositional satisfiability, Minimum disclosure proofs of knowledge, A satisfiability tester for non-clausal propositional calculus, Feasible arithmetic computations: Valiant's hypothesis, Optimal product design using conjoint analysis: Computational complexity and algorithms, On the number of iterations of local improvement algorithms, Optimizing propositional calculus formulas with regard to questions of deducibility, The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\), A weight-balanced branching rule for SAT, Stratification and knowledge base management, Positive relativizations of the \(P=?\) NP problem, Tautology testing with a generalized matrix reduction method, ``A posteriori evaluation of bin packing approximation algorithms, The node-deletion problem for hereditary properties is NP-complete, On finding minimal length superstrings, Structure preserving reductions among convex optimization problems, Relational consistency algorithms and their application in finding subgraph and graph isomorphisms, Solving parity games by a reduction to SAT, Lower bounds on the size of sweeping automata, Complexity of spanning tree problems: Part I, Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete, Fast simplifications for Tarski formulas based on monomial inequalities, Automatic model construction, Heuristics and their design: A survey, A note on a theorem of Blum, Shub, and Smale, Complexity results for classes of quantificational formulas, The maximum value problem and NP real numbers, A syntax-based approach to measuring the degree of inconsistency for belief bases, An appraisal of computational complexity for operations researchers, Optimization, approximation, and complexity classes, Cook versus Karp-Levin: Separating completeness notions if NP is not small, Succinct circuit representations and leaf language classes are basically the same concept, The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness, Combination techniques and decision problems for disunification, Automorphisms in the PTIME-Turing degrees of recursive sets, On the theory of average case complexity, A guide to completeness and complexity for modal logics of knowledge and belief, Integer programs for logic constraint satisfaction, Matching theory -- a sampler: From Dénes König to the present, On the SPANNING \(k\)-TREE problem, An efficient algorithm for the 3-satisfiability problem, Local search and the local structure of NP-complete problems, Nondiamond theorems for polynomial time reducibility, Structure identification in relational data, The multicovering problem, The interconnection problem, Exclusive and essential sets of implicates of Boolean functions, Approximation algorithms for combinatorial problems, A versatile system for computer-controlled assembly, An observation on time-storage trade off, NP-complete scheduling problems, Space-bounded reducibility among combinatorial problems, A comparison of polynomial time reducibilities, Polynomial and abstract subrecursive classes, On the equivalence, containment, and covering problems for the regular and context-free languages, A characterization of the power of vector machines, Satisfiability of algebraic circuits over sets of natural numbers, Riemann's hypothesis and tests for primality, Ordered vertex removal and subgraph problems, NP-complete decision problems for binary quadratics, Nondeterminism and Boolean operations in pda's, An algorithm for the quadratic assignment problem using Benders' decomposition, On the complexity of some two-person perfect-information games, On splitting recursive sets, Lower bounds on the worst-case complexity of some oracle algorithms, Candidate keys for relations, Graph isomorphism, general remarks, On the theory of the PTIME degrees of the recursive sets, Properties of uniformly hard languages, A simplified NP-complete satisfiability problem, A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets, On self-reducibility and weak P-selectivity, Edge-contraction problems, Consistency in nondeterministic storage, The complexity of the satisfiability problem for Krom formulas, Refutational theorem proving using term-rewriting systems, Probabilistic approach to the satisfiability problem, Games against nature, Completeness in approximation classes, Configuration landscape analysis and backbone guided local search. I: Satisfiability and maximum satisfiability
