<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-088

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

M.S. Joy and V.J. Rayward-Smith, NP-Completeness of a Combinator Optimisation Problem (January 1, 1987).

Abstract

We consider a deterministic rewrite system for combinatory logic over combinators S, K, I, B, C, S', B' and C'. Terms will be represented by graphs so that reduction of a duplicator will cause the duplicated expression to be "shared" rather than copied. To each normalising term we assign a weighting which is the number of reduction steps necessary to reduce the expression to normal form. A lambda expression may be represented by several distinct expressions in combinatory logic, and two combinatory logic expressions are considered equivalent if they represent the same lambda expression (up to beta-eta-equivalence). The problem of minimising the number of reduction steps over equivalent combinator expressions (i.e. the problem of finding the "fastest running" combinator representation for a specific lambda expression) is proved to be NP-complete by reduction from the "Hitting Set" problem.

<%@ include file="cited.html" %>

M.S. Joy and V.J. Rayward-Smith, "NP-Completeness of a Combinator Optimisation Problem", Notre Dame Journal of Formal Logic 36(2), pp. 319-335 (1995)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>