UCLNLP/adversarial_qa huggingface dataset:
Computational_complexity_theory

It is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not really the case, since function problems can be recast as decision problems. For example, the multiplication of two integers can be expressed as the set of triples (a, b, c) such that the relation a × b = c holds. Deciding whether a given triple is a member of this set corresponds to solving the problem of multiplying two numbers.

Question: What is the name of a container used to protect something?

Question: Regarding a problem, what is the action for finding an answer to said problem?

Question: Regarding the alphabet taught in the United States, what letter comes after B?

Question: What is the name for the verb when an actor changes roles in a play or production?

Question: The second letter of the English Alphabet is?

Question: The mathematical sign given to the word equal is?

Question: What is term for an individual when they are a part of a group or organization?

Question: A man that is comparatively much wealthier than another individual is said to be what?

Question: The symbol used to signify multiplying or multiplication is?
Computational_complexity_theory

A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a thought experiment representing a computing machine—anything from an advanced supercomputer to a mathematician with a pencil and paper. It is believed that if a problem can be solved by an algorithm, there exists a Turing machine that solves the problem. Indeed, this is the statement of the Church–Turing thesis. Furthermore, it is known that everything that can be computed on other models of computation known to us today, such as a RAM machine, Conway's Game of Life, cellular automata or any programming language can be computed on a Turing machine. Since Turing machines are easy to analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine is the most commonly used model in complexity theory.

Question: How frequently are Turing machines employed in complexity theory?

Question: A Turing machine models what type of object?

Question: What is a Turing machine *not*?

Question: Who is the physicist for whom the machine is named?

Question: The general idea of the Church-Turing thesis is what?
Computational_complexity_theory

Many machine models different from the standard multi-tape Turing machines have been proposed in the literature, for example random access machines. Perhaps surprisingly, each of these models can be converted to another without providing any extra computational power. The time and memory consumption of these alternate models may vary. What all these models have in common is that the machines operate deterministically.

Question: Why is a random access machine brought up?

Question: How many types of machines have been suggested?

Question: How have the suggestions been made?

Question: What are written works that are often on a particular subject or topic called?

Question: The father of theoretical computer science and AI is considered to be whom?

Question: How much effort would the conversion take?

Question: An adverb that describes refers to something being in addition to a main item is?
Computational_complexity_theory

Many types of Turing machines are used to define complexity classes, such as deterministic Turing machines, probabilistic Turing machines, non-deterministic Turing machines, quantum Turing machines, symmetric Turing machines and alternating Turing machines. They are all equally powerful in principle, but when resources (such as time or space) are bounded, some of these may be more powerful than others.

Question: What kind of Turing machines are equally powerful?

Question: What could have more or less power depending upon circumstances?

Question: When do some Turing machinesperform better than others?

Question: What characteristic do Turing machines share?

Question: How powerful are Turing machines?

Question: What is important when deciding which Turing machine to use?

Question: It's impossible to predict what state probabilistic and alternating Turing machines will end up in, making them what type of overarching Turing machine?

Question: What might be constrained when using a Turing machine?

Question: What type of Turing machine listed in this article would most likely use an undirected graph (i.e. path A-B-C is the same as C-B-A)?

Question: What is a difference between the Turing machines?
Computational_complexity_theory

The most commonly used reduction is a polynomial-time reduction. This means that the reduction process takes polynomial time. For example, the problem of squaring an integer can be reduced to the problem of multiplying two integers. This means an algorithm for multiplying two integers can be used to square an integer. Indeed, this can be done by giving the same input to both inputs of the multiplication algorithm. Thus we see that squaring is not more difficult than multiplication, since squaring can be reduced to multiplication.

Question: Two mathematical operations that are effectively the same in difficulty is the process of multiplying and what operation?

Question: What is another example of a polynomial-time reduction method?

Question: Multiplication requires the prescence of at least what involved in the mathematical operation?

Question: The time required to solve an equation, whereas time is defined by a specific expression is often referred to as what?

Question: In what other way can squaring an integer be done?

Question: Squaring is a good way to demonstrate what process in mathematics?
Computational_complexity_theory

A deterministic Turing machine is the most basic Turing machine, which uses a fixed set of rules to determine its future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits. The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. Algorithms that use random bits are called randomized algorithms. A non-deterministic Turing machine is a deterministic Turing machine with an added feature of non-determinism, which allows a Turing machine to have multiple possible future actions from a given state. One way to view non-determinism is that the Turing machine branches into many possible computational paths at each step, and if it solves the problem in any of these branches, it is said to have solved the problem. Clearly, this model is not meant to be a physically realizable model, it is just a theoretically interesting abstract machine that gives rise to particularly interesting complexity classes. For examples, see non-deterministic algorithm.

Question: Who was themathematician and computer scientist that developed the concept of algorithms?

Question: What serves as the base of both probabilistic and non-deterministic Turing machines

Question: If a set of items are ordered unpredictably, or without a given set of rules or pattern, it is said to be?

Question: What is the descriptor for an item that is secure in place, and cannot be moved?

Question: Parts of a shrub that grows out from the trunk or stem are called?
Computational_complexity_theory

For example, consider the deterministic sorting algorithm quicksort. This solves the problem of sorting a list of integers that is given as the input. The worst-case is when the input is sorted or sorted in reverse order, and the algorithm takes time O(n2) for this case. If we assume that all possible permutations of the input list are equally likely, the average time taken for sorting is O(n log n). The best case occurs when each pivoting divides the list in half, also needing O(n log n) time.

Question: Which scenario takes time O(n log n), when the input is sorted in reverse order, or when each pioting divides the list in half?

Question: What way of sorting can be accomplished in a maximum of n2 time?

Question: What technique works best when its pivots split the input into equal lists?

Question: Which scenario takes time O(n2), when the input is sorted in reverse order, or when each pioting divides the list in half?

Question: Which scenario takes an amount of time more similar to the average time, when the input is sorted in reverse order, or when each pioting divides the list in half?
Computational_complexity_theory

Many known complexity classes are suspected to be unequal, but this has not been proved. For instance P ⊆ NP ⊆ PP ⊆ PSPACE, but it is possible that P = PSPACE. If P is not equal to NP, then P is not equal to PSPACE either. Since there are many known complexity classes between P and PSPACE, such as RP, BPP, PP, BQP, MA, PH, etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.

Question: If two items are not equal in size or value, they are then called?

Question: The term used at the end of a list to give the idea that more and similar items are to mentioned or included is?

Question: The 16th letter of the English alphabet is?

Question: A person usually has what number of noses on their face?
Computational_complexity_theory

As Fortnow & Homer (2003) point out, the beginning of systematic studies in computational complexity is attributed to the seminal paper "On the Computational Complexity of Algorithms" by Juris Hartmanis and Richard Stearns (1965), which laid out the definitions of time and space complexity and proved the hierarchy theorems. Also, in 1965 Edmonds defined a "good" algorithm as one with running time bounded by a polynomial of the input size.

Question: Who produced a work closer to 1995, Fortnow & Homer or Juris Hartmanis and Richard Stearns?

Question: Who wrote the seminal paper which is considered the beginning of the systematic studies in computational complexities?

Question: Who laid out the definitions of time and space complexities?

Question: Who produced a work closer to 1960, Fortnow & Homer or Juris Hartmanis and Richard Stearns?

Question: Which two people did not contribute a work in 1965, but instead contributed a work nearly 40 years later?

Question: What did Hartmanis and Stearns define in 1965?

Question: Who is responsible for the  beginning of systematic studies on computational complexities?

Question: WHat proved the hierarchy theorems?
Computational_complexity_theory

When considering computational problems, a problem instance is a string over an alphabet. Usually, the alphabet is taken to be the binary alphabet (i.e., the set {0,1}), and thus the strings are bitstrings. As in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, and graphs can be encoded directly via their adjacency matrices, or by encoding their adjacency lists in binary.

Question: What must be done prior to performing computations with an alphabet?

Question: What are two examples of mathematical objects in computation?

Question: What type of data does not need encoding?
Computational_complexity_theory

An example of a decision problem is the following. The input is an arbitrary graph. The problem consists in deciding whether the given graph is connected, or not. The formal language associated with this decision problem is then the set of all connected graphs—of course, to obtain a precise definition of this language, one has to decide how graphs are encoded as binary strings.

Question: What kind of definition of the language is desired?

Question: What kind of conundrum is discussed in the article?
Computational_complexity_theory

Many complexity classes are defined using the concept of a reduction. A reduction is a transformation of one problem into another problem. It captures the informal notion of a problem being at least as difficult as another problem. For instance, if a problem X can be solved using an algorithm for Y, X is no more difficult than Y, and we say that X reduces to Y. There are many different types of reductions, based on the method of reduction, such as Cook reductions, Karp reductions and Levin reductions, and the bound on the complexity of reductions, such as polynomial-time reductions or log-space reductions.

Question: When does X become reduced to Y?

Question: What are problems solved by?

Question: A reduction is a what kind of idea?

Question: If problem X can be solved by algorithm Y, what happens to X?

Question: What are Cook and Karp?

Question: Many different transformations of one problem into another exist, also known as?

Question: In a reduction, both problems should be equally?
Computational_complexity_theory

The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. This hypothesis is called the Cobham–Edmonds thesis. The complexity class NP, on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the Boolean satisfiability problem, the Hamiltonian path problem and the vertex cover problem. Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.

Question: A device that can use a set of rules and an input to determine a result, although said device is hypothetical is referred to as what?

Question: There is complexity class P and another one called what?

Question: What is learned from Turing machines?

Question: A set of rules that are often used by a computer to problem solve is called a what?

Question: Computationial tasks is modeled by what?

Question: If a computer cannot use an algorithm to solve a set of problems, then these are considered nondeterministic polynomial time unlike what complexity category?

Question: An algorithm that can exhibit different behaviors in multiple runs even when using the same input is referred to as?
Computational_complexity_theory

Even though some proofs of complexity-theoretic theorems regularly assume some concrete choice of input encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding. This can be achieved by ensuring that different representations can be transformed into each other efficiently.

Question: The two sides of proofs include abstract thought and what else.

Question: The act of converting data into a more encrypted or enciphered form is referred to as?

Question: A composite material used in construction of buildings or other structures for longetivity and strength is called?

Question: Mathematical arguments for a statement that essentially gurantee that said statement gurantees a given conclusion are called?

Question: An item that exists equivalent to a thought or idea and is not physical in nature, but rather incorporeal is given which adjective?

Question: Does the text recommend choice to be concrete or abstract.
Computational_complexity_theory

The integer factorization problem is the computational problem of determining the prime factorization of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a factor less than k. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the RSA algorithm. The integer factorization problem is in NP and in co-NP (and even in UP and co-UP). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP will equal co-NP). The best known algorithm for integer factorization is the general number field sieve, which takes time O(e(64/9)1/3(n.log 2)1/3(log (n.log 2))2/3) to factor an n-bit integer. However, the best known quantum algorithm for this problem, Shor's algorithm, does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.

Question: Which of the following is not an algorithm: RSA, NP, or general number field sieve?

Question: Which of the following is not a classification for problems: NP, co-NP, or RSA?

Question: Which of the following is not someone's last name: Shor or RSA?
Normans

Normandy was the site of several important developments in the history of classical music in the 11th century. Fécamp Abbey and Saint-Evroul Abbey were centres of musical production and education. At Fécamp, under two Italian abbots, William of Volpiano and John of Ravenna, the system of denoting notes by letters was developed and taught. It is still the most common form of pitch representation in English- and German-speaking countries today. Also at Fécamp, the staff, around which neumes were oriented, was first developed and taught in the 11th century. Under the German abbot Isembard, La Trinité-du-Mont became a centre of musical composition.

Question: what is the last type of person mentioned?

Question: what is the last place mentioned?

Question: what is the second place mentioned?

Question: what is the third place mentioned?

Question: what is the first place mentioned?
Normans

The customary law of Normandy was developed between the 10th and 13th centuries and survives today through the legal systems of Jersey and Guernsey in the Channel Islands. Norman customary law was transcribed in two customaries in Latin by two judges for use by them and their colleagues: These are the Très ancien coutumier (Very ancient customary), authored between 1200 and 1245; and the Grand coutumier de Normandie (Great customary of Normandy, originally Summa de legibus Normanniae in curia laïcali), authored between 1235 and 1245.

Question: What has prevailed?

Question: Which of the following is not a Channel Island: Jersey, Normandy, or Guernsey?

Question: what happend in the 12th century according to the passage?

Question: Which was earlier, the earliest possible date for the Tres ancien coutumier or the latest possible date for the Grand coutumier de Normandie?

Question: Which was earlier, the latest possible date for the Tres ancien coutumier or the earliest possible date for the Grand coutumier de Normandie?
Normans

Soon after the Normans began to enter Italy, they entered the Byzantine Empire and then Armenia, fighting against the Pechenegs, the Bulgars, and especially the Seljuk Turks. Norman mercenaries were first encouraged to come to the south by the Lombards to act against the Byzantines, but they soon fought in Byzantine service in Sicily. They were prominent alongside Varangian and Lombard contingents in the Sicilian campaign of George Maniaces in 1038–40. There is debate whether the Normans in Greek service actually were from Norman Italy, and it now seems likely only a few came from there. It is also unknown how many of the "Franks", as the Byzantines called them, were Normans and not other Frenchmen.

Question: Where did the Normans go after the Byzantine Empire?

Question: What is being said about the Norman Italy soldiers known as Franks?

Question: What was done to someone  by the Norman's on the final stop on their trek?
Normans

The English name "Normans" comes from the French words Normans/Normanz, plural of Normant, modern French normand, which is itself borrowed from Old Low Franconian Nortmann "Northman" or directly from Old Norse Norðmaðr, Latinized variously as Nortmannus, Normannus, or Nordmannus (recorded in Medieval Latin, 9th century) to mean "Norseman, Viking".

Question: Who calls them Normans?

Question: What language ultimately led to the French word Norsman?

Question: What language ultimately led to the English name Normans?

Question: What does English name Normans mean?

Question: What is another ultimate meaning of the English name Normans?

Question: What would one Norman be called?
Normans

The Norman dynasty had a major political, cultural and military impact on medieval Europe and even the Near East. The Normans were famed for their martial spirit and eventually for their Christian piety, becoming exponents of the Catholic orthodoxy into which they assimilated. They adopted the Gallo-Romance language of the Frankish land they settled, their dialect becoming known as Norman, Normaund or Norman French, an important literary language. The Duchy of Normandy, which they formed by treaty with the French crown, was a great fief of medieval France, and under Richard I of Normandy was forged into a cohesive and formidable principality in feudal tenure. The Normans are noted both for their culture, such as their unique Romanesque architecture and musical traditions, and for their significant military accomplishments and innovations. Norman adventurers founded the Kingdom of Sicily under Roger II after conquering southern Italy on the Saracens and Byzantines, and an expedition on behalf of their duke, William the Conqueror, led to the Norman conquest of England at the Battle of Hastings in 1066. Norman cultural and military influence spread from these new European centres to the Crusader states of the Near East, where their prince Bohemond I founded the Principality of Antioch in the Levant, to Scotland and Wales in Great Britain, to Ireland, and to the coasts of north Africa and the Canary Islands.

Question: What are the Normans celebrated for other than their culture, Romanesque architecture, martial spirit, Christian piety, military accomplishments, and innovations?

Question: Where did the Norman's get their language?

Question: Who was a Norman military person who was admired by Normans?

Question: What are the Normans celebrated for other than their culture, musical traditions, martial spirit, Christian piety, military accomplishments, and innovations?
Normans

The further decline of Byzantine state-of-affairs paved the road to a third attack in 1185, when a large Norman army invaded Dyrrachium, owing to the betrayal of high Byzantine officials. Some time later, Dyrrachium—one of the most important naval bases of the Adriatic—fell again to Byzantine hands.

Question: Dyrrachium was on the?
Normans

Several families of Byzantine Greece were of Norman mercenary origin during the period of the Comnenian Restoration, when Byzantine emperors were seeking out western European warriors. The Raoulii were descended from an Italo-Norman named Raoul, the Petraliphae were descended from a Pierre d'Aulps, and that group of Albanian clans known as the Maniakates were descended from Normans who served under George Maniaces in the Sicilian expedition of 1038.

Question: Where did Norman mercenary families of Byzantine Greece come from?

Question: What group mentioned did not srise from Pierre d'Aulps or the Italo-Norman Raoul?

Question: In addition to the Raoulli and the Petraliphae, what mercenary group arose in Greece during the Comnenian Restoration?

Question: What are Raoul,  Pierre d'Aulps and  George Maniaces?

Question: What was the nationality of the George Maniaces?

Question: The Comnenian Restoration gave rise to such mercenary groups as the Raoulli, the Maniakates and the what?

Question: When did Normans work for Mr. Maniaces?

Question: What part of Byzantine Greece did the Maniakates settle?