paper available by FTP

• To: types
• Subject: paper available by FTP
• From: Patrick Lincoln <lincoln@Theory.Stanford.EDU>
• Date: Wed, 02 Sep 92 11:49:55 EDT
• Sender: meyer@theory.lcs.mit.edu

Date: Tue, 1 Sep 92 10:14:03 -0700
To: linear@cs.stanford.edu

        Constant-Only Multiplicative Linear Logic is NP-Complete
                        P. Lincoln  and  T. Winkler

    This paper explores the decision problem for 
    multiplicative linear logic without propositions.  The
    fragment is shown to be NP-Complete.  Reduction from 
    3-Partition is used to demonstrate hardness, while 
    the obvious "guess and check entire proof" procedure
    shows that this decision problem is in NP.  This result
    lends evidence that the linear circuit evaluation problem
    (testing validity of expressions in AND, OR, TRUE, and FALSE
    in multiplicative linear logic) is intractable.  This paper
    is based on work by the authors and N. Shankar, as well as 
    earlier work by Girard and others.
	
% ftp ftp.csl.sri.com
Name: anonymous
Password:  <<your e-mail address>>
ftp> cd pub/lincoln
ftp> binary
ftp> get comult-npc.dvi  
ftp> quit

• Prev: Paper available by ftp
• Next: Category Theory and Computer Science, Sep. 7-10, '93, Amsterdam
• Index(es):
  • Main
  • Thread