NP-completeness of a combinator optimization problem

DOI10.1305/NDJFL/1040248462zbMATH Open0837.03015OpenAlexW2091336525MaRDI QIDQ1903594FDOQ1903594

Authors: M. S. Joy, V. J. Rayward-Smith 

Publication date: 13 May 1996

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1305/ndjfl/1040248462

Recommendations

• NP-completeness of the linear complementarity problem
• scientific article; zbMATH DE number 6832021
• scientific article; zbMATH DE number 1944142
• NP for Combinatorialists
• Optimization and \(\mathrm{NP}_{\mathbb{R}}\)-completeness of certain fewnomials
• Inapproximability of combinatorial optimization problems
• scientific article; zbMATH DE number 847149
• Decidability of NP-complete problems
• The complexity of some complementation problems
• COMPLEXITY PROBLEMS IN ENUMERATIVE COMBINATORICS

zbMATH Keywords

normal formcombinatory logicNP-completedeterministic rewrite systemlambda- expression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Combinatory logic and lambda calculus (03B40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatory logic. With two sections by William Craig.
• The lambda calculus, its syntax and semantics
• Combinatory logic. Vol. II
• Title not available (Why is that?)
• A new implementation technique for applicative languages
• Title not available (Why is that?)
• Another algorithm for bracket abstraction
• Title not available (Why is that?)

Cited In (10)

• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• Combinatorial flexibility problems and their computational complexity
• LaserTank is NP-Complete
• NP-completeness of some optimal sequencing problems with a given grouping of elements
• NP-completeness of the Hamming salesman problem
• Max NP-completeness made easy
• On the complexity of alpha conversion
• Title not available (Why is that?)
• Metaheuristics: A bibliography
• Title not available (Why is that?)

This page was built for publication: NP-completeness of a combinator optimization problem

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