BISC: Intractability Principle

From: masoud nikravesh (nikraves@eecs.berkeley.edu)
Date: Tue Jul 03 2001 - 19:54:55 MET DST

  • Next message: Jonathan G. Campbell: "Re: Neuro-Fuzzy with categorical input?"

    *********************************************************************
    Berkeley Initiative in Soft Computing (BISC)
    *********************************************************************

    Intractability Principle
    Lotfi A. Zadeh

    July 2,2001

      Abstract*

          Almost all scientific theories are based on Aristotelean logic and

    probability theory. Use of these theories has led to brilliant successes

    that are visible to all. But what is less visible is that alongside
    the brilliant successes lie many problem areas where progress has been
    slow or nonexistent. We cannot automate driving in city traffic; we
    cannot construct programs which can summarize nonstereotypical
    stories,and our capacity to do economic forecasting without human
    intervention leaves much to be desired.

          To understand the reasons for the mixed picture, it is germane to
    start with the thesis that, in general, a system for performing a
    specified task may be viewed as having three principal components: (a)
    hardware; (b) software: and (c) what may be called brainware -- a
    complex of concepts, theories, methods and algorithms which govern the
    functioning of hardware and software.

          The capability of a system to perform a specified task is a
    function of the capabilities of its hardware, software and brainware
    components. In general, there is a tradeoff between these
    capabilities. However, there are important classes of problems in which
    the overall capability is limited primarily by the structure of
    brainware and, more particularly, by the underlying systems for logical
    reasoning and dealing with uncertainty.

          What may be called the Intractability Principle is a thesis which
    relates limits on performance to the structure of brainware. Stated
    informally, the thesis has two parts, (a)negative; and (b)
    positive,which are simmarized in the following.
            (a) As the complexity of a problem increases, a critical
    threshold is reached beyond which solution cannot be achieved through
    the use of techniques based on two-valued logical systems and
    probability theory.
            (b) Beyond the critical threshold, ahievement of solution
    necessitates the use of fuzzy-logic-based methodology of computing with
    words (CW) and perception-based theory of probabilistic reasoning (PTp).

          The basic idea which underlies the Intractability Principle is
    that problems which lie beyond the critical threshold are intractable by

    conventional measurement-based methods .What is not widely recognized is

    that many problems which are simple for humans fall into this category.
    Here are a few examples.

          (a) Automation of driving a car. In this case, on one end of the
    complexity scale we have automation of driving on a freeway with no
    traffic. On the other end, is automation of driving in Istambul. Humans
    can do this without any measurements and any computations. At this
    juncture, no conceivable system can solve the problem.

          (b) Machine -execution of the instruction: Make a right turn at
    the intersection. In this case, at one end of the scale we have an
    intersection on the outskirts of Princeton. On the other end, an
    intersection in the center of New York.

          (c) Summarization. On one end of the scale is a short
    stereotypical story. On the other end, is a book. As a task,
    summarization is an order of magnitude more complex than machine
    translation.

           There are two key points that require comment. First, in most
    real-world problems that are simple for humans, the critical threshold
    is not a remote limit that is of no concern. On the contrary, it
    underscores the intrinsic limitation of techniqus based on Aristotelian
    logic and proability theory to deal with problems in which
    decision-relevant information is, for the most part, perception-based.

           The second point relates to the pivotal role of the methodology
    of computing with words in making it possible to solve problems which
    lie beyond the critical threshold. The crux of the matter is that in
    most problems which lie beyond the critical threshold, perception-based

    information is described by propositions expressed in a natural
    language, e.g., " usually traffic is very heavy in late afternoon." In
    general, such propositions are f-granular in the sense that (a) the
    boundaries of perceived classes are unsharp; and (b) the values of
    attributes are granulated ,with a granule being a clump of values drawn
    together by indistinguishability, similarity, proximity and
    functionality. The problem with theories based on Aristotelian logic
    and probability theory is that they do not have the capability to deal
    with f-granular propositions drawn from a natural language. The
    importance of computing with words derives from the fact that it does
    provide this capability.

          A key concept in computing with words is that of Precisiated
    Natural Language (PNL). Basically, PNL is a subset of a natural
    language, NL, which consists of propositions which are precisiable
    through translation into what is called the Generalized Constraint
    Language, GCL. PNL serves an important function as a definition
    language ,with the language of fuzzy if-then rules being a sublanguage
    of PNL.

          Computing with words provides a basis for an important
    generalization of probability theory -- from standard probability
    theory, PT, to perception-based probability theory, PTp. Separately and
    in combination, computing with words and perception-based theory of
    probabilistic reasoning open the door to solution of problems which lie
    beyond the critical threshold. This is the principal rationale for the
    positive thesis of the Intractability Principle.

    _______________________________________________________________________
    * Professor in the Graduate School and director, Berkeley Initiative in

    Soft Computing (BISC), Computer Science Division and the Electronics
    Research Laboratory, Department of EECS, University of California,
    Berkeley, CA 94720-l776; Telephone: 5l0-642-4959; Fax: 5l0-642-l7l2;
    E-mail: zadeh@cs.berkeley.edu. Researh supported in part by ONR
    Contract N000l4-99-C-0298, NASA Contract NCC2-l006, NASA Grant NAC2-ll7,

    ONR Grant NOOOl4-96-l-0556, ONR Grant FDNOOl499l035, ARO Grand DAAH
    04-96l-034l and the BISC Program of UC Berkeley.

    --
    Professor in the Graduate School, Computer Science Division
    Department of Electrical Engineering and Computer Sciences
    University of California
    Berkeley, CA 94720 -1776
    Director, Berkeley Initiative in Soft Computing (BISC)
    

    Address: Computer Science Division University of California Berkeley, CA 94720-1776 Tel(office): (510) 642-4959 Fax(office): (510) 642-1712 Tel(home): (510) 526-2569 Fax(home): (510) 526-2433, (510) 526-5181 zadeh@cs.berkeley.edu http://www.cs.berkeley.edu/People/Faculty/Homepages/zadeh.html

    -------------------------------------------------------------------- If you ever want to remove yourself from this mailing list, you can send mail to <Majordomo@EECS.Berkeley.EDU> with the following command in the body of your email message: unsubscribe bisc-group or from another account, unsubscribe bisc-group <your_email_adress>

    ############################################################################ This message was posted through the fuzzy mailing list. (1) To subscribe to this mailing list, send a message body of "SUB FUZZY-MAIL myFirstName mySurname" to listproc@dbai.tuwien.ac.at (2) To unsubscribe from this mailing list, send a message body of "UNSUB FUZZY-MAIL" or "UNSUB FUZZY-MAIL yoursubscription@email.address.com" to listproc@dbai.tuwien.ac.at (3) To reach the human who maintains the list, send mail to fuzzy-owner@dbai.tuwien.ac.at (4) WWW access and other information on Fuzzy Sets and Logic see http://www.dbai.tuwien.ac.at/ftp/mlowner/fuzzy-mail.info (5) WWW archive: http://www.dbai.tuwien.ac.at/marchives/fuzzy-mail/index.html



    This archive was generated by hypermail 2b30 : Tue Jul 03 2001 - 20:11:18 MET DST