BISC: Lotfi A. Zadeh

From: masoud nikravesh (
Date: Thu Oct 11 2001 - 23:03:55 MET DST

  • Next message: Editors at "Hot Products & More on Next Week"

    Berkeley Initiative in Soft Computing (BISC)

    BISC Seminar

     Lotfi A. Zadeh
    BISC Program
    EECS-CS Division
    UC Berkeley

     Oct 18, 2001
     373 Soda Hall
    4:00-5:30 pm

    Intractability Principle and the Concept of Z-hardness
    Lotfi A. Zadeh


          Almost all scientific theories are based on Aristotelian 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 non-stereotypical 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
    is focused on problems which are solvable by humans but are difficult
    for machines. More specifically, the principle relates
    machine-solvability to the structure of brainware. A basic concept which
    underlies the principle is that of a qualitative complexity scale, or
    QCS for short. The low end of QCS consists of problem/tasks which are
    easy to solve/perform. The opposite holds for the high end. An M-scale
    is a QCS which applies to machines; an H-scale applies to humans. For
    simplicity, QCS is assumed to be linearly ordered; it can be partially
    ordered, if needed. An example of M-scale is automation of driving a
    car. At the low end is the problem of automation of driving on a freeway
    with no traffic. At the high end, automation of driving in Istanbul.

    Stated informally, the thesis has two parts, (a) negative; and (b)
    positive, which are summarized 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. On an M-scale, problems which lie to the right of
    the critical threshold are said to be Z-hard.
            (b) Beyond the critical threshold, achievement 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 of Z-hard problems.

          (a) Automation of driving a car. In this case, as stated already,
    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
    Istanbul. Humans can drive in Istanbul without any measurements and any
    computations. At this juncture, no conceivable system can solve the
    problem of automation of driving in Istanbul.

          (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. In (a), (b), and (c), problems at the end of the scale are

           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 techniques based on Aristotelian
    logic and probability 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., "traffic is usually 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. In large
    measure, 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, Department of EECS,
    University of California, Berkeley, CA 94720-l776; Telephone:
    5l0-642-4959; Fax: 5l0-642-l7l2;
    Research 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 Grant 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

    -------------------------------------------------------------------- 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 (2) To unsubscribe from this mailing list, send a message body of "UNSUB FUZZY-MAIL" or "UNSUB FUZZY-MAIL" to (3) To reach the human who maintains the list, send mail to (4) WWW access and other information on Fuzzy Sets and Logic see (5) WWW archive:

    This archive was generated by hypermail 2b30 : Thu Oct 11 2001 - 23:28:38 MET DST