In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values. An example of a decision problem is deciding. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either ` no' depending upon the values of x and y. 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. One such algorithm is long division. If the remainder is zero the answer is'yes', otherwise it is'no'. A decision problem which can be solved by an algorithm is called decidable. Decision problems 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; 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, categorizes undecidable decision problems by Turing degree, a measure of the noncomputability inherent in any solution. A decision problem is a yes-or-no question on an infinite set of inputs, it is traditional to define the decision problem as the set of possible inputs together with the set of inputs for which the answer is yes. These inputs can be natural numbers, but can be values of some other kind, like binary strings or strings over some other alphabet; the subset of strings for which the problem returns "yes" is a formal language, decision problems are defined as formal languages. 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. A classic example of a decidable decision problem is the set of prime numbers.

It is possible to 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. A decision problem A is decidable or solvable if A is a recursive set. A problem is decidable, solvable, or provable if A is a recursively enumerable set. Problems that are not decidable are undecidable. For those it is not possible to create an algorithm, efficient or otherwise; the halting problem is an important undecidable decision problem. Decision problems can be ordered according to many-one reducibility and related to 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 theory 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. Decision problems are 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?". A function problem consists of a partial function f; every function problem can be turned into a decision problem. If this decision problem were solvable 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 when the function is not computable in polynomial time; the function f = 2x 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 the associated decision problem is decidable.

However, this reduction is more liberal than the standard reduction used in computational complexity. Unlike decision problems, for which there is only one correct answer for each input, optimization problems are concerned with finding the best answer to a particular input. Optimization problems arise in many applications, such as the traveling salesman problem and many questions in linear programming. There are standard techniques for transforming function and optimization problems into decision problems. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight; the associated decision problem is: for each N, to decide whether the graph has any tour with weight less than N. By answering the decision problem, it is pos

Stalag Luft III was a Luftwaffe-run prisoner of war camp during the Second World War, which held captured Western Allied air force personnel. The camp was established in March 1942 in the German province of Lower Silesia near the town of Sagan, 160 kilometres south-east of Berlin; the site was selected. It is best known for two escape plots by Allied POWs, one in 1943 that became the basis of a fictionalised film, The Wooden Horse, based on a book by escapee Eric Williams; the second breakout—the so-called Great Escape—of March 1944, was conceived by Royal Air Force Squadron Leader Roger Bushell, was authorised by the senior British officer at Stalag Luft III, Herbert Massey. A fictionalised version of the escape was depicted in the film The Great Escape, based on a book by former prisoner Paul Brickhill; the camp was liberated by Soviet forces in January 1945. The German military followed a practice whereby each branch of the military was responsible for the POWs of equivalent branches. Hence the Luftwaffe was responsible for any Allied aircrew taken prisoner.

This included captured naval aviators, such as members of the British Fleet Air Arm. In a few cases, other non-air force personnel were held at Stalag Luft III. Stammlager Luft was Luftwaffe nomenclature for a POW camp. While the camp held only POWs who were officers, it was not known by the usual terms for such camps – Offizier Lager or Oflag, and camp expansions added compounds for non-commissioned officers. The first compound of the camp was completed and opened on 21 March 1942; the first POWs, or kriegies, as they called themselves, to be housed at Stalag Luft III were British and other Commonwealth officers, arriving in April 1942. The Centre Compound was opened on 11 April 1942 and held British and other Commonwealth NCOs; the North Compound for British airmen, opened on 29 March 1943. A South Compound for Americans was opened in September 1943 and USAAF prisoners began arriving at the camp in significant numbers the following month and the West Compound was opened in July 1944 for U. S. officers.

Each compound consisted of fifteen single-story huts. Each 3.0-by-3.7-metre bunkroom slept fifteen men in five triple-deck bunks. The camp grew to 24 hectares in size and housed about 2,500 Royal Air Force officers, about 7,500 U. S. Army Air Forces, about 900 officers from other Allied air forces, for a total of 10,949 inmates, including some support officers; the prison camp had a number of design features that made escape difficult. The digging of escape tunnels, in particular, was made difficult by several factors: the barracks housing the prisoners were raised 60 centimetres off the ground to make it easier for guards to detect tunnelling; the loose, collapsible sand meant the structural integrity of any tunnel would be poor. A third defence against tunnelling was the placement of seismograph microphones around the perimeter of the camp, which were expected to detect any sounds of digging. A substantial library with schooling facilities was available, where many POWs earned degrees such as languages, engineering or law.

The exams were supplied by the Red Cross and supervised by academics such as a Master of King's College, a POW in Luft III. The prisoners built a theatre and put on high-quality bi-weekly performances featuring all the current West End shows; the prisoners used the camp amplifier to broadcast a news and music radio station they named Station KRGY, short for Kriegsgefangener and published two newspapers, the Circuit and the Kriegie Times, which were issued four times a week. POWs operated a system whereby newcomers to the camp were vetted, to prevent German agents from infiltrating their ranks. Any POW who could not be vouched for by two POWs who knew the prisoner by sight was interrogated and afterwards escorted continually by other prisoners, until such time as he was deemed to be a genuine Allied POW. Several infiltrators were discovered by this method and none is known to have escaped detection in Luft III; the German guards were referred to by POWs as "goons" and, unaware of the Allied connotation, willingly accepted the nickname after being told it stood for "German Officer Or Non-Com".

German guards were followed everywhere they went by prisoners, who used an elaborate system of signals to warn others of their location. The guards' movements were carefully recorded in a logbook kept by a rota of officers. Unable to stop what the prisoners called the "Duty Pilot" system, the Germans allowed it to continue and on one occasion the book was used by Kommandant von Lindeiner to bring charges against two guards who had slunk away from duty several hours early; the camp's 800 Luftwaffe guards were either too old for combat duty or young men convalescing after long tours of duty or from wounds. Because the guards were Luftwaffe personnel, the prisoners were accorded far better treatment than that granted to other POWs in Germany. Deputy Commandant Major Gustav Simoleit, a professor of history and ethnology before the war, spoke several languages, including English, Russian and Czech. Tra

In various parts of economics, the term free disposal implies that resources can be discarded without any cost. For example, a fair division setting with free disposal is a setting where some resources have to be divided but some of the resources may be left undivided, discarded or donated. Examples of situations with free disposal are allocation of food, clothes jewels etc. Examples of situations without free disposal are: Chore division -. Allocation of land with an old structure - since the structure may have to be destructed, destruction is costly. Allocation of an old car - since the car may have to be carried away to used cars garage, moving it may be costly. Allocation of shares in a firm that may have debts - since the firm cannot be disposed of without paying its debts first; the free disposal assumption may be useful for several reasons: It enables truthful cake-cutting algorithms: The option to discard some of the cake gives the players an incentive to reveal their true valuations.

It enables fast envy-free cake-cutting algorithms, more economically-efficient envy-free allocations: Discarding some of the cake helps to reduce envy. It enables online assignment algorithms