A decision problem has only two possible outputs, yes or no (or alternately 1 or 0) on any input.

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem. The answer can be either 'yes' or 'no', and depends upon the values of x and y.

Decision problems typically appear in mathematical questions of decidability, that is, the question of the existence of an effective method to determine the existence of some object or its membership in a set; many of the important problems in mathematics are undecidable.

Decision problems are closely related to function problems, which can have answers that are more complex than a simple 'yes' or 'no'. A corresponding function problem is "given two numbers x and y, what is x divided by y?". They are also related to optimization problems, which are concerned with finding the best answer to a particular problem.

A method for solving a decision problem given in the form of an algorithm is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would give the steps for determining whether x evenly divides y, given x and y. One such algorithm is long division, taught to many school children. If the remainder is zero the answer produced is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm, such as this example, is called decidable.

The field of computational complexity categorizes decidable decision problems by how difficult they are to solve. "Difficult", in this sense, is described in terms of the computational resources needed by the most efficient algorithm for a certain problem. The field of recursion theory, meanwhile, categorizes undecidable decision problems by Turing degree, which is a measure of the noncomputability inherent in any solution.

Research in computability theory has typically focused on decision problems. As explained in the section Equivalence with function problems below, there is no loss of generality.

Definition[link]

A decision problem is any arbitrary yes-or-no question on an infinite set of inputs. Because of this, it is traditional to define the decision problem equivalently as: the set of inputs for which the problem returns yes.

These inputs can be natural numbers, but may also be values of some other kind, such as strings over the binary alphabet {0,1} or over some other finite set of symbols. The subset of strings for which the problem returns "yes" is a formal language, and often decision problems are defined in this way as formal languages.

Alternatively, using an encoding such as Gödel numberings, any string can be encoded as a natural number, via which a decision problem can be defined as a subset of the natural numbers.

Examples[link]

A classic example of a decidable decision problem is the set of prime numbers. It is possible to effectively decide whether a given natural number is prime by testing every possible nontrivial factor. Although much more efficient methods of primality testing are known, the existence of any effective method is enough to establish decidability.

Decidability[link]

A decision problem A is called decidable or effectively solvable if A is a recursive set. A problem is called partially decidable, semidecidable, solvable, or provable if A is a recursively enumerable set. Problems that are not decidable are called undecidable.

The halting problem is an important undecidable decision problem; for more examples, see list of undecidable problems.

Complete problems[link]

Decision problems can be ordered according to many-one reducibility and related feasible reductions such as polynomial-time reductions. A decision problem P is said to be complete for a set of decision problems S if P is a member of S and every problem in S can be reduced to P. Complete decision problems are used in computational complexity to characterize complexity classes of decision problems. For example, the Boolean satisfiability problem is complete for the class NP of decision problems under polynomial-time reducibility.

History[link]

The Entscheidungsproblem, German for "Decision-problem", is attributed to David Hilbert: "At [the] 1928 conference Hilbert made his questions quite precise. First, was mathematics complete... Second, was mathematics consistent... And thirdly, was mathematics decidable? By this he meant, did there exist a definite method which could, in principle be applied to any assertion, and which was guaranteed to produce a correct decision on whether that assertion was true" (Hodges, p. 91). Hilbert believed that "in mathematics there is no ignorabimus' (Hodges, p. 91ff) meaning 'there is no limit to what can be known'. See David Hilbert and Halting Problem for more.

Equivalence with function problems[link]

A function problem consists of a partial function f; the informal "problem" is to compute the values of f on the inputs for which it is defined.

Every function problem can be turned into a decision problem; the decision problem is just the graph of the associated function. (The graph of a function f is the set of pairs (x,y) such that f(x) = y.) If this decision problem were effectively solvable then the function problem would be as well. This reduction does not respect computational complexity, however. For example, it is possible for the graph of a function to be decidable in polynomial time (in which case running time is computed as a function of the pair (x,y) ) when the function is not computable in polynomial time (in which case running time is computed as a function of x alone). The function f(x) = 2^x has this property.

Every decision problem can be converted into the function problem of computing the characteristic function of the set associated to the decision problem. If this function is computable then the associated decision problem is decidable. However, this reduction is more liberal than the standard reduction used in computational complexity (sometimes called polynomial-time many-one reduction); for example, the complexity of the characteristic functions of an NP-complete problem and its co-NP-complete complement is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.

Practical decision[link]

Having practical decision procedures for classes of logical formulas is of considerable interest for program verification and circuit verification. Pure Boolean logical formulas are usually decided using SAT-solving techniques based on the DPLL algorithm. Conjunctive formulas over linear real or rational arithmetic can be decided using the simplex algorithm, formulas in linear integer arithmetic (Presburger arithmetic) can be decided using Cooper's algorithm or William Pugh's Omega test. Formulas with negations, conjunctions and disjunctions combine the difficulties of satisfiability testing with that of decision of conjunctions; they are generally decided nowadays using SMT-solving technique, which combine SAT-solving with decision procedures for conjunctions and propagation techniques. Real polynomial arithmetic, also known as the theory of real closed fields, is decidable, for instance using the cylindrical algebraic decomposition; unfortunately the complexity of that algorithm is excessive for most practical uses.

A leading scientific conference in this field is Computer Aided Verification.

See also[link]

• ALL (complexity)
• Computational problem
• Decidability (logic) – for the problem of deciding whether a formula is a consequence of a logical theory.
• yes-no question
• Optimization problem
• Search problem
• Counting problem (complexity)
• Function problem
• Word problem (mathematics)

References[link]

• Hanika, Jiri. Search Problems and Bounded Arithmetic. PhD Thesis, Charles University, Prague. http://www.eccc.uni-trier.de/static/books/Search_Problems_and_Bounded_Arithmetic/
• Hodges, A., Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for some more history that led to Turing's work.

Hodges references a biography of David Hilbert: Constance Reid, Hilbert (George Allen & Unwin; Springer-Verlag, 1970). There are apparently more recent editions.

• Kozen, D.C. (1997), Automata and Computability, Springer.
• Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
• Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
• Robert I. Soare (1987), Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7

Effective decision[link]

• Daniel Kroening & Ofer Strichman, Decision procedures, Springer, ISBN 978-3-540-74104-6
• Aaron Bradley & Zohar Manna, The calculus of computation, Springer, ISBN 978-3-540-74112-1

Dale Breckenridge Carnegie
146px
Born	(1888-11-24)November 24, 1888 Maryville, Missouri1
Died	November 1, 1955(1955-11-01) (aged 66) Forest Hills, New York
Occupation	Writer, lecturer
Notable work(s)	How to Win Friends and Influence People
Spouse(s)	Lolita Baucaire (1927–1937) Dorothy Price Vanderpool (1944–1955)
Children	Donna Dale Carnegie
Signature

Dale Breckenridge Carnegie (originally Carnagey until 1922 and possibly somewhat later) (November 24, 1888 – November 1, 1955) was an American writer, lecturer, and the developer of famous courses in self-improvement, salesmanship, corporate training, public speaking, and interpersonal skills. Born into poverty on a farm in Missouri, he was the author of How to Win Friends and Influence People (1936), a massive bestseller that remains popular today. He also wrote How to Stop Worrying and Start Living (1948), Lincoln the Unknown (1932), and several other books.

One of the core ideas in his books is that it is possible to change other people's behavior by changing one's reaction to them.

Biography[link]

Dale Carnegie was born in 1888 in Maryville, Missouri, Carnegie was a poor farmer's boy, the second son of James William Carnagey (b. Indiana, February 1852 – living 1910) and wife Amanda Elizabeth Harbison (b. Missouri, February 1858 – living 1910). His family moved to Belton, Missouri when he was a small child. In his teens, though still having to get up at 4 a.m. every day to milk his parents' cows, he managed to obtain an education at the State Teacher's College in Warrensburg. His first job after college was selling correspondence courses to ranchers; then he moved on to selling bacon, soap and lard for Armour & Company. He was successful to the point of making his sales territory of South Omaha, Nebraska, the national leader for the firm.^[1]

After saving $500, Dale Carnegie quit sales in 1911 in order to pursue a lifelong dream of becoming a Chautauqua lecturer. He ended up instead attending the American Academy of Dramatic Arts in New York, but found little success as an actor, though it is written that he played the role of Dr. Hartley in a road show of Polly of the Circus.^[2] When the production ended, he returned to New York, unemployed, nearly broke, and living at the YMCA on 125th Street. It was there that he got the idea to teach public speaking, and he persuaded the "Y" manager to allow him to instruct a class in return for 80% of the net proceeds. In his first session, he had run out of material; improvising, he suggested that students speak about "something that made them angry", and discovered that the technique made speakers unafraid to address a public audience.^[3] From this 1912 debut, the Dale Carnegie Course evolved. Carnegie had tapped into the average American's desire to have more self-confidence, and by 1914, he was earning $500 – the equivalent of nearly $10,000 now – every week.

Perhaps one of Carnegie’s most successful marketing moves was to change the spelling of his last name from “Carnagey” to Carnegie, at a time when Andrew Carnegie (unrelated) was a widely revered and recognized name. By 1916, Dale was able to rent Carnegie Hall itself for a lecture to a packed house.^[4] Carnegie's first collection of his writings was Public Speaking: a Practical Course for Business Men (1926), later entitled Public Speaking and Influencing Men in Business (1932). His crowning achievement, however, was when Simon & Schuster published How to Win Friends and Influence People. The book was a bestseller from its debut in 1936,^[5] in its 17th printing within a few months.^[4] By the time of Carnegie's death, the book had sold five million copies in 31 languages, and there had been 450,000 graduates of his Dale Carnegie Institute.^[6] It has been stated in the book that he had critiqued over 150,000 speeches in his participation in the adult education movement of the time.^[7] During World War I he served in the U.S. Army.^[8]

His first marriage ended in divorce in 1931. On November 5, 1944, in Tulsa, Oklahoma, he married Dorothy Price Vanderpool, who also had been divorced. Vanderpool had two daughters; Rosemary, from her first marriage, and Donna Dale from their marriage together.

Carnegie died at his home in Forest Hills, New York.^[9] He was buried in the Belton, Cass County, Missouri, cemetery. The official biography from Dale Carnegie & Associates, Inc. states that he died of Hodgkin's disease, complicated with uremia, on November 1, 1955.^[10]

How to Win Friends and Influence People[link]

Written in 1936, How to Win Friends and Influence People is still a popular book to date in business and Business Communication skills. Dale Carnegie's four part book is packed with advice to create success in business and personal lives. How to Win Friends and Influence People is a tool used in Dale Carnegie Training and includes the following parts:

1. Part One: Fundamental Techniques in Handling People
2. Part Two: Six Ways to Make People Like You
3. Part Three: How to Win People to Your Way of Thinking
4. Part Four: Be a Leader - How to Change People Without Giving Offense or Arousing Resentment

Dale Carnegie Training[link]

Dale Carnegie Course in Effective Speaking and Human Relations is learn-by-doing based program for individuals based on Dale Carnegie's teachings. It was founded in 1912 and is represented in more than 80 countries. More than 8 million people have completed Dale Carnegie Training.^[5]

The course comprises a proprietary process that uses team dynamics and intra-group activities to strengthen interpersonal relations, manage stress and handle fast-changing workplace conditions. Other subjects included are communication, creative problem-solving and focused leadership.

The course is based on a five-phase continuous improvement cycle:

1. Build greater self-confidence
2. Strengthen people skills
3. Enhance communication skills
4. Develop leadership skills
5. Improve our attitude and reducing stress

Dale Carnegie Training in Japan[link]

On July 24, 1939, Carnegie made his first visit to Japan. Invited by the Japanese Board of Tourist Industry and Japanese Government Railways in an effort to improve communications and cultural understanding between the America and Japan, Carnegie arrived on a self-described "Relaxation Tour."^[11]

After his steam ship docked in Yokohama, he made his way to the famous Imperial Hotel in Tokyo. From July 24 to July 30, he met representatives from the Foreign Ministry in Tokyo and the Nichi Nichi Tokyo newspaper in Karuizawa. On July 31, he was the guest of honour giving a talk on human relations at a special luncheon held at the American Club in Tokyo.^[11]

Carnegie’s travels continued as far south as Shimonoseki, visiting Miyanoshita, Kawana, Atami, Gamagori, Gifu, Yamada, Toba, Nara, Kyoto and Hiroshima along the way. During the course of his visit, he had stayed at the Fujiya Hotel in Miyanoshita City, the Nara Hotel in Nara City, the Tokiwa Kan in Gamagori, the Nagaragawa Hotel in Gifu, visited the Ise Shrine in Mie Prefecture and observed the Mikimoto pearl fisheries in Toba. ^[11]

On August 6, he took a steamboat from Shimonoseki to Pusan, Korea where he embarked on a brief tour of the country, eventually making his way to Beijing and Shanghai.^[11]

On September 1, 1939, he made his second visit to Japan before returning home. This time he visited the Daibutsu in Kamakura and again stayed at the Imperial Hotel. He departed for America on September 4, 1939.^[11]

In July 1953, Carnegie made his third visit to Japan, meeting friends from his previous visit and taking time to enjoy the sights of Kyoto.^[12]

In 1963 Dale Carnegie Training was launched in Japan. Edwin Whitlow, from Hawaii acted as a sponsor for Frank Mochizuki, until he could take over the running of Dale Carnegie in Japan by himself. Whitlow died on March 8, 1980 on a visit to Oregon, after having been hit by a car.^[13]

Frank Mochizuki eventually retired and was succeeded by Tokugen Yamamoto in 1994, until his sudden death in 1995.^[14] His wife, Yukiko Yamamoto, took over the responsibilities for Carnegie in Japan until 2007 when she retired. Craig Kirkwood succeeded Mrs. Yamamoto and in 2010 he passed the responsibility for Dale Carnegie in Japan to Dr. Greg Story.

Quotes[link]

Wikiquote has a collection of quotations related to: Dale Carnegie

"The ideas I stand for are not mine. I borrowed them from Socrates. I swiped them from Chesterfield. I stole them from Jesus. And I put them in a book. If you don't like their rules whose would you use?"

"The essence of all art is to take pleasure in giving pleasure."

"I am very fond of strawberries and cream, but I have found that for some strange reason, fish prefer worms. So when I went fishing, I didn’t think about what I wanted. I thought about what they wanted. I didn't bait the hook with strawberries and cream. Rather, I dangled a worm or grasshopper in front of the fish."

"People rarely succeed unless they have fun in what they are doing."

Books[link]

• 1915: Art of Public Speaking ^[15], with Joseph Berg Esenwein.
• 1920: Public Speaking: the Standard Course of the United Y. M. C. A. Schools ^[16].
• 1926: Public Speaking: a Practical Course for Business Men ^[17]. Later editions and updates changed the name of the book several times: Public Speaking and Influencing Men in Business (1937 revised) ^[18], How to Develop Self-Confidence and Influence People by Public Speaking (1956) ^[19] and Public Speaking for Success (2005) ^[20].
• 1932: Lincoln, the Unknown ^[21].
• 1934: Little Known Facts About Well Known People ^[22].
• 1936: How to Win Friends and Influence People ^[23].
• 1937: Five Minute Biographies ^[24].
• 1944: Dale Carnegie's Biographical round-up ^[25].
• 1948: How to Stop Worrying and Start Living ^[26].
• 1959: Dale Carnegie's Scrapbook: a Treasury of the Wisdom of the Ages ^[27]. A selection of Dale Carnegie's writings edited by Dorothy Carnegie.
• 1962: The Quick and Easy Way to Effective Speaking ^[28]. The fourth revision of Public speaking and influencing men in business, by Dorothy Carnegie, based upon Dale Carnegie's own notes and ideas but a very different book than original.

Booklets[link]

(most given out in Dale Carnegie Courses)

• 1938: How to Get Ahead in the World Today
• 1936: The Little Golden Book (later renamed The Golden Book, lists basics from HTWFIP and HTSPSL)
• 1940s: How to Put Magic in the Magic Formula
• 1947: A Quick and Easy Way to Learn to Speak in Public. (later combined as Speak More Effectively, 1979)
• 1952: How to Make Our Listeners Like Us ^[29]. (later combined as Speak More Effectively, 1979)
• 1959: How to Save Time and Get Better Results in Conferences (later renamed Meetings: Quicker & Better Results)
• 1960: How to Remember Names (later renamed as Remember Names)
• 1965: The Little Recognized Secret of Success (later renamed Live Enthusiastically)
• 1979: Apply Your Problem Solving Know How

Footnotes[link]

External links[link]

• Popular Quotes by Dale Carnegie
• Dale Carnegie Videos
• Dale Carnegie on findagrave.com
• The Art of Public Speaking (free download)
• Dale Carnegie Training
• Dale Carnegie Quotes in English and Hindi

Films

• As himself in 1947 film titled Jiggs and Maggie in Society