|
Seinosuke Toda
is a computer scientist working at the Nihon University in Tokyo. Toda earned his Ph.D. from the Tokyo Institute of Technology in 1992, under the supervision of Kojiro Kobayashi. He was a recipient of the 1998 Gödel Prize for proving Toda's theorem in computational complexity theory, which states that every problem in the polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ... has a polynomial-time Turing reduction to a counting problem. Notes Japanese computer scientists 20th-century Japanese mathematicians 21st-century Japanese mathematicians Theoretical computer scientists Gödel Prize laureates 1959 births Living people Academic staff of Nihon University {{Compu-scientist-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nihon University
, abbreviated as , is a private research university in Japan. Its predecessor, Nihon Law School (currently the Department of Law), was founded by Yamada Akiyoshi, the Minister of Justice, in 1889. It is one of Japan's leading private universities. The university's name is derived from the Japanese word "Nihon" meaning Japan. Nihon University now has "16 colleges and 87 departments, 20 postgraduate schools, 1 junior college which is composed of 5 departments, 1 correspondence division, 32 research institutes and 3 hospitals." The number of students exceeds 70,000 and is the largest in Japan. University profile Most of the university's campuses are in the Kantō region, the vast majority in Tokyo or surrounding areas, although two campuses are as far away from Tokyo as Shizuoka Prefecture and Fukushima Prefecture. These campuses mostly accommodate single colleges or schools ( in Japanese). In December 2016 the university acquired the former Newcastle Court House in , New S ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tokyo
Tokyo (; ja, 東京, , ), officially the Tokyo Metropolis ( ja, 東京都, label=none, ), is the capital and List of cities in Japan, largest city of Japan. Formerly known as Edo, its metropolitan area () is the most populous in the world, with an estimated 37.468 million residents ; the city proper has a population of 13.99 million people. Located at the head of Tokyo Bay, the prefecture forms part of the Kantō region on the central coast of Honshu, Japan's largest island. Tokyo serves as Economy of Japan, Japan's economic center and is the seat of both the Government of Japan, Japanese government and the Emperor of Japan. Originally a fishing village named Edo, the city became politically prominent in 1603, when it became the seat of the Tokugawa shogunate. By the mid-18th century, Edo was one of the most populous cities in the world with a population of over one million people. Following the Meiji Restoration of 1868, the imperial capital in Kyoto was mov ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tokyo Institute Of Technology
is a national research university located in Greater Tokyo Area, Japan. Tokyo Tech is the largest institution for higher education in Japan dedicated to science and technology, one of first five Designated National University and selected as a Top Type university of Top Global University Project by the Japanese government. It is generally considered to be one of the most prestigious universities in Japan. Tokyo Tech's main campus is located at Ōokayama on the boundary of Meguro and Ota, with its main entrance facing the Ōokayama Station. Other campuses are located in Suzukakedai and Tamachi. Tokyo Tech is organised into 6 schools, within which there are over 40 departments and research centres. Tokyo Tech enrolled 4,734 undergraduates and 1,464 graduate students for 2015–2016. It employs around 1,100 faculty members. Tokyo Institute of Technology produced a Nobel Prize laureate in Chemistry Hideki Shirakawa Ph.D. History Foundation and early years (1881–1922) ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory ( ACM SIGACT). The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time. The Gödel Prize has been awarded since 1993. The prize is awarded either at STOC (ACM Symposium on Theory of Computing, one of the main North American conferences in theoretical computer science) or ICALP ( International Colloquium on Automata, Languages and Programming, one of the main Europe Europe is a large peninsula conventionally considered a continent in its own ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Toda's Theorem
Toda's theorem is a result in computational complexity theory that was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998 Gödel Prize. Statement The theorem states that the entire polynomial hierarchy PH is contained in PPP; this implies a closely related statement, that PH is contained in P#P. Definitions #P is the problem of exactly counting the number of solutions to a polynomially-verifiable question (that is, to a question in NP), while loosely speaking, PP is the problem of giving an answer that is correct more than half the time. The class P#P consists of all the problems that can be solved in polynomial time if you have access to instantaneous answers to any counting problem in #P (polynomial time relative to a #P oracle). Thus Toda's theorem implies that for any problem in the polynomial hierarchy there is a deterministic polynomial-time Turing reduction to a counting problem. An analogous result in the c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Complexity Theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of compu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial Hierarchy
In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH. Classes within the hierarchy have complete problems (with respect to polynomial-time reductions) which ask if quantified Boolean formulae hold, for formulae with restrictions on the quantifier order. It is known that equality between classes on the same level or consecutive levels in the hierarchy would imply a "collapse" of the hierarchy to that level. Definitions There are multiple equivalent definitions of the classes of the polynomial hierarchy. Oracle definition For the or ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial-time Turing Reduction
In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming or reducing it to inputs for the second problem and calling the subroutine one or more times. If both the time required to transform the first problem to the second, and the number of times the subroutine is called is polynomial, then the first problem is polynomial-time reducible to the second. A polynomial-time reduction proves that the first problem is no more difficult than the second one, because whenever an efficient algorithm exists for the second problem, one exists for the first problem as well. By contraposition, if no efficient algorithm exists for the first problem, none exists for the second either. Polynomial-time reductions are frequently used in complexity theory for defining both complexity classes and complete problems ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Counting Problem (complexity)
In computational complexity theory and computability theory, a counting problem is a type of computational problem. If ''R'' is a search problem then :c_R(x)=\vert\\vert \, is the corresponding counting function and :\#R=\ denotes the corresponding decision problem. Note that ''cR'' is a search problem while #''R'' is a decision problem, however ''cR'' can be ''C'' Cook-reduced to #''R'' (for appropriate ''C'') using a binary search (the reason #''R'' is defined the way it is, rather than being the graph of ''cR'', is to make this binary search possible). Counting complexity class If ''NX'' is a complexity class associated with non-deterministic machines then ''#X'' = is the set of counting problems associated with each search problem in ''NX''. In particular, #P is the class of counting problems associated with NP search problems. Just as NP has NP-complete problems via many-one reduction In computability theory and computational complexity theory, a many-one reduct ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Japanese Computer Scientists
Japanese may refer to: * Something from or related to Japan, an island country in East Asia * Japanese language, spoken mainly in Japan * Japanese people, the ethnic group that identifies with Japan through ancestry or culture ** Japanese diaspora, Japanese emigrants and their descendants around the world * Japanese citizens, nationals of Japan under Japanese nationality law ** Foreign-born Japanese, naturalized citizens of Japan * Japanese writing system, consisting of kanji and kana * Japanese cuisine, the food and food culture of Japan See also * List of Japanese people * * Japonica (other) * Japonicum * Japonicus This list of Latin and Greek words commonly used in systematic names is intended to help those unfamiliar with classical languages to understand and remember the scientific names of organisms. The binomial nomenclature used for animals and plants i ... * Japanese studies {{disambiguation Language and nationality disambiguation pages ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
21st-century Japanese Mathematicians
The 1st century was the century spanning AD 1 ( I) through AD 100 ( C) according to the Julian calendar. It is often written as the or to distinguish it from the 1st century BC (or BCE) which preceded it. The 1st century is considered part of the Classical era, epoch, or historical period. The 1st century also saw the appearance of Christianity. During this period, Europe, North Africa and the Near East fell under increasing domination by the Roman Empire, which continued expanding, most notably conquering Britain under the emperor Claudius (AD 43). The reforms introduced by Augustus during his long reign stabilized the empire after the turmoil of the previous century's civil wars. Later in the century the Julio-Claudian dynasty, which had been founded by Augustus, came to an end with the suicide of Nero in AD 68. There followed the famous Year of Four Emperors, a brief period of civil war and instability, which was finally brought to an end by Vespasian, ninth Roman emperor ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
