Leonid Levin (original) (raw)
Leonid Levin (russisch Леони́д Анато́льевич Ле́вин, Leonid Anatoljewitsch Lewin; * 2. November 1948 in Dnepropetrowsk, Ukrainische SSR) ist ein sowjetisch-amerikanischer Informatiker.
| Property | Value |
|---|---|
| dbo:abstract | Leonid Levin (russisch Леони́д Анато́льевич Ле́вин, Leonid Anatoljewitsch Lewin; * 2. November 1948 in Dnepropetrowsk, Ukrainische SSR) ist ein sowjetisch-amerikanischer Informatiker. (de) Leonid Anatólievich Levin Леонид Анатольевич Левин (nació el 2 de noviembre de 1948 en la antigua URSS). Es informático, estudió siguiendo los pasos de Andréi Kolmogórov. Leonid obtuvo su primer doctorado en 1972 en la universidad de Moscú. Más adelante, emigró a los EE. UU. en 1978 y obtuvo otro doctorado en el Instituto Tecnológico de Massachusetts en 1979. Es muy conocido por su trabajo en la computación aleatoria, en la complejidad de los algorítmicos, en los fundamentos de las matemáticas e informática, en la teoría del cómputo y en la teoría de la información. Su vida se describe en un capítulo del libro: Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. Levin descubrió un teorema que también fue descubierto y probado por Stephen Cook. Este teorema de Cook-Levin, nombrado a menudo así por los investigadores, era una base para uno de los siete problemas matemáticos del milenio recompensado por el Clay Mathematics Institute con un premio de un millón de dólares. El artículo de Levin sobre este teorema fue publicado en 1973; había dado una conferencia de sus ideas algunos años antes, aunque los resultados de la escritura formal ocurrieron después de la publicación de Stephen Cook. Levin es actualmente profesor de informática en la universidad de Boston, donde comenzó a impartir clases en el año 1980. (es) Leonid Anatolievich Levin (/leɪ.oʊˈniːd ˈlɛvɪn/ lay-oh-NEED LEV-in; Russian: Леони́д Анато́льевич Ле́вин; Ukrainian: Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American mathematician and computer scientist. He is known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory. He obtained his master's degree at Moscow University in 1970 where he studied under Andrey Kolmogorov and completed the Candidate Degree academic requirements in 1972. He and Stephen Cook independently discovered the existence of NP-complete problems. This NP-completeness theorem, often called the Cook–Levin theorem, was a basis for one of the seven Millennium Prize Problems declared by the Clay Mathematics Institute with a $1,000,000 prize offered. The Cook–Levin theorem was a breakthrough in computer science and an important step in the development of the theory of computational complexity. Levin was awarded the Knuth Prize in 2012 for his discovery of NP-completeness and the development of average-case complexity.He is a member of the US National Academy of Sciences anda fellow of the American Academy of Arts and Sciences. (en) Leonid Anatolievich Levin (russe : Леонид Анатольевич Левин, né le 2 novembre 1948 à Dnipropetrovsk, RSS d'Ukraine) est un informaticien et logicien russo-ukraino-américain. Il est connu notamment pour avoir découvert la notion de NP-complétude en même temps que Stephen Cook et pour des résultats renforçant les théorèmes d'incomplétude de Gödel. (fr) 레오니드 아나톨리에비치 레빈(영어: Leonid Anatolievich Levin, 러시아어: Леони́д Анато́льевич Ле́вин 레오니트 아나톨리예비치 레빈[*], 우크라이나어: Леоні́д Анато́лійович Ле́він 레오니드 아나톨리요비치 레빈[*], 1948년 11월 2일 ~ )은 소비에트 연방 드네프로페트로프스크(현 우크라이나의 드니프로페트로우스크)에서 출생한 전산학자, 수학자이다. 안드레이 콜모고로프의 제자였다. 1978년에 미국 국적을 얻어 현재 미국에 거주하고 있다. 전산학의 이론적 기반을 연구하면서 계산이론, 정보 이론 등에서 많은 업적을 남겼다. 특히 스티븐 쿡이 발견한 NP-완전을 1973년에 독자적으로 발견했다. ‘쿡의 정리’ 혹은 ‘쿡-레빈 정리’라고 부르는 이 정리는 전산학 분야의 획기적 발견이며, 계산 복잡도 이론의 중요한 이론적 기반이다. (ko) Leonid Anatolievich Levin, em russo: Леонид Анатольевич Левин; (Dnipropetrovsk, 2 de novembro de 1948) é um informático soviético-estadunidense. Obteve o mestrado em 1970 e um Ph.D. em 1972 na Universidade de Moscou, onde foi aluno de Andrey Kolmogorov. Em 1978 emigrou para os Estados Unidos, obtendo um Ph.D. no Instituto de Tecnologia de Massachusetts (MIT) em 1979. Seu orientador no MIT foi Albert Ronald Meyer. Levin e Stephen Cook, descobriram a existência de problemas NP-completos. Este teorema da NP-completude, muitas vezes chamado de Teorema de Cook-Levin, foi a base para um dos sete Problemas do Milênio. O teorema de Cook-Levin foi um avanço na ciência da computação e é o fundamento da complexidade computacional. Atualmente é professor de ciência da computação na Universidade de Boston, onde começou a lecionar em 1980. (pt) Леони́д Анато́льевич Ле́вин (род. 2 ноября 1948, Днепропетровск) — советский и американский математик, специалист в области теории вычислительной сложности. Профессор информатики в Бостонском университете. Член Национальной академии наук США (2019). (ru) Леонід Анатолійович Левін (нар. 2 листопада 1948, Дніпропетровськ) — радянський і американський математик, фахівець в області теорії обчислювальної складності. Професор інформатики в Бостонському університеті. (uk) |
| dbo:academicDiscipline | dbr:Computer_Science dbr:Mathematics |
| dbo:almaMater | dbr:Massachusetts_Institute_of_Technology dbr:Moscow_University |
| dbo:award | dbr:Knuth_Prize |
| dbo:birthDate | 1948-11-02 (xsd:date) |
| dbo:birthPlace | dbr:Dnipropetrovsk dbr:Soviet_Union dbr:Ukrainian_SSR |
| dbo:knownFor | dbr:Cook–Levin_theorem dbr:Randomness dbr:Average-case_complexity |
| dbo:thumbnail | wiki-commons:Special:FilePath/LeonidLevin2010.jpg?width=300 |
| dbo:wikiPageExternalLink | https://www.cs.bu.edu/fac/lnd/ http://genealogy.math.ndsu.nodak.edu/id.php%3Fid=17519 http://www.math.nsc.ru/LBRT/g2/english/ssk/levin_e.html |
| dbo:wikiPageID | 402708 (xsd:integer) |
| dbo:wikiPageLength | 8129 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1059602690 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Millennium_Prize_Problems dbr:Boris_Trakhtenbrot dbr:Boston_University dbr:Algorithmic_probability dbc:Knuth_Prize_laureates dbr:United_States dbc:Living_people dbc:Massachusetts_Institute_of_Technology_alumni dbr:Computer_Science dbr:Analysis_of_algorithms dbr:Massachusetts_Institute_of_Technology dbr:Mathematics dbr:Russian_Academy_of_Sciences dbr:Clay_Mathematics_Institute dbr:Cook–Levin_theorem dbr:Andrey_Kolmogorov dbr:Stephen_Cook dbr:Computational_complexity_theory dbr:Computer_science dbr:Computer_scientist dbr:Computing dbc:Scientists_from_Dnipro dbr:Theory_of_computation dbr:Mathematician dbc:1948_births dbc:20th-century_American_mathematicians dbc:21st-century_American_mathematicians dbc:American_computer_scientists dbc:American_people_of_Ukrainian-Jewish_descent dbc:Moscow_State_University_alumni dbc:Ukrainian_Jews dbr:Albert_R._Meyer dbr:American_Academy_of_Arts_and_Sciences dbr:Knuth_Prize dbr:Randomness dbc:21st-century_Russian_politicians dbc:American_information_theorists dbc:Boston_University_faculty dbc:Soviet_emigrants_to_the_United_States dbc:Soviet_mathematicians dbc:Ukrainian_mathematicians dbc:Russian_mathematicians dbc:Russian_computer_scientists dbc:Russian_information_theorists dbc:Soviet_computer_scientists dbr:Dnipropetrovsk dbr:Average-case_complexity dbr:Soviet_Union dbr:Information_theory dbr:National_Academy_of_Sciences dbr:Candidate_of_Sciences dbr:NP-completeness dbr:Ukrainian_SSR dbr:Moscow_University dbr:Independently_discovered |
| dbp:almaMater | dbr:Massachusetts_Institute_of_Technology dbr:Moscow_University |
| dbp:birthDate | 1948-11-02 (xsd:date) |
| dbp:birthPlace | dbr:Dnipropetrovsk dbr:Soviet_Union dbr:Ukrainian_SSR |
| dbp:caption | Leonid Levin in 2010 (en) |
| dbp:field | dbr:Computer_Science dbr:Mathematics |
| dbp:knownFor | dbr:Cook–Levin_theorem dbr:Average-case_complexity Research in complexity, randomness, information (en) |
| dbp:name | Leonid Anatolievich Levin (en) |
| dbp:prizes | Knuth Prize (en) |
| dbp:wikiPageUsesTemplate | dbt:Authority_control dbt:Cite_web dbt:Commons_category dbt:IPAc-en dbt:Reflist dbt:Respell dbt:Short_description dbt:Small dbt:Birth_date_and_age dbt:Nowraplinks dbt:Infobox_scientist dbt:Knuth_Prize_laureates |
| dbp:workInstitution | dbr:Boston_University |
| dcterms:subject | dbc:Knuth_Prize_laureates dbc:Living_people dbc:Massachusetts_Institute_of_Technology_alumni dbc:Scientists_from_Dnipro dbc:1948_births dbc:20th-century_American_mathematicians dbc:21st-century_American_mathematicians dbc:American_computer_scientists dbc:American_people_of_Ukrainian-Jewish_descent dbc:Moscow_State_University_alumni dbc:Ukrainian_Jews dbc:21st-century_Russian_politicians dbc:American_information_theorists dbc:Boston_University_faculty dbc:Soviet_emigrants_to_the_United_States dbc:Soviet_mathematicians dbc:Ukrainian_mathematicians dbc:Russian_mathematicians dbc:Russian_computer_scientists dbc:Russian_information_theorists dbc:Soviet_computer_scientists |
| gold:hypernym | dbr:Scientist |
| schema:sameAs | http://viaf.org/viaf/70440154 |
| rdf:type | owl:Thing foaf:Person dbo:Person dul:NaturalPerson wikidata:Q19088 wikidata:Q215627 wikidata:Q5 wikidata:Q729 yago:WikicatAmericanComputerScientists yago:WikicatAmericanInformationTheorists yago:WikicatAmericanMathematicians yago:WikicatAmericanPeople yago:WikicatAmericanPeopleOfRussian-JewishDescent dbo:Animal dbo:Eukaryote dbo:Scientist dbo:Species yago:WikicatComputerScientists schema:Person yago:WikicatLivingPeople yago:WikicatMoscowStateUniversityAlumni yago:WikicatPeopleFromDnipropetrovsk yago:WikicatRussianComputerScientists yago:WikicatRussianInformationTheorists yago:WikicatRussianMathematicians yago:WikicatSovietComputerScientists yago:WikicatSovietEmigrantsToTheUnitedStates yago:WikicatSovietMathematicians yago:WikicatSovietPeople wikidata:Q901 yago:Acquirer109764201 yago:Alumnus109786338 yago:Associate109816771 yago:CausalAgent100007347 yago:Colleague109935990 yago:ComputerScientist109951070 yago:ComputerUser109951274 yago:Emigrant110051975 yago:Honoree110183757 yago:Intellectual109621545 yago:Laureate110249011 yago:LivingThing100004258 yago:Mathematician110301261 yago:Migrant110314952 yago:Object100002684 yago:Organism100004475 yago:Peer109626238 yago:Person100007846 yago:PhysicalEntity100001930 yago:Recipient109627906 yago:WikicatKnuthPrizeLaureates yago:YagoLegalActor yago:YagoLegalActorGeo yago:Scholar110557854 yago:Scientist110560637 yago:Theorist110706812 yago:Traveler109629752 yago:Whole100003553 yago:WikicatAlexanderVonHumboldtFellows umbel-rc:Scientist |
| rdfs:comment | Leonid Levin (russisch Леони́д Анато́льевич Ле́вин, Leonid Anatoljewitsch Lewin; * 2. November 1948 in Dnepropetrowsk, Ukrainische SSR) ist ein sowjetisch-amerikanischer Informatiker. (de) Leonid Anatolievich Levin (russe : Леонид Анатольевич Левин, né le 2 novembre 1948 à Dnipropetrovsk, RSS d'Ukraine) est un informaticien et logicien russo-ukraino-américain. Il est connu notamment pour avoir découvert la notion de NP-complétude en même temps que Stephen Cook et pour des résultats renforçant les théorèmes d'incomplétude de Gödel. (fr) 레오니드 아나톨리에비치 레빈(영어: Leonid Anatolievich Levin, 러시아어: Леони́д Анато́льевич Ле́вин 레오니트 아나톨리예비치 레빈[*], 우크라이나어: Леоні́д Анато́лійович Ле́він 레오니드 아나톨리요비치 레빈[*], 1948년 11월 2일 ~ )은 소비에트 연방 드네프로페트로프스크(현 우크라이나의 드니프로페트로우스크)에서 출생한 전산학자, 수학자이다. 안드레이 콜모고로프의 제자였다. 1978년에 미국 국적을 얻어 현재 미국에 거주하고 있다. 전산학의 이론적 기반을 연구하면서 계산이론, 정보 이론 등에서 많은 업적을 남겼다. 특히 스티븐 쿡이 발견한 NP-완전을 1973년에 독자적으로 발견했다. ‘쿡의 정리’ 혹은 ‘쿡-레빈 정리’라고 부르는 이 정리는 전산학 분야의 획기적 발견이며, 계산 복잡도 이론의 중요한 이론적 기반이다. (ko) Леони́д Анато́льевич Ле́вин (род. 2 ноября 1948, Днепропетровск) — советский и американский математик, специалист в области теории вычислительной сложности. Профессор информатики в Бостонском университете. Член Национальной академии наук США (2019). (ru) Леонід Анатолійович Левін (нар. 2 листопада 1948, Дніпропетровськ) — радянський і американський математик, фахівець в області теорії обчислювальної складності. Професор інформатики в Бостонському університеті. (uk) Leonid Anatólievich Levin Леонид Анатольевич Левин (nació el 2 de noviembre de 1948 en la antigua URSS). Es informático, estudió siguiendo los pasos de Andréi Kolmogórov. Leonid obtuvo su primer doctorado en 1972 en la universidad de Moscú. Más adelante, emigró a los EE. UU. en 1978 y obtuvo otro doctorado en el Instituto Tecnológico de Massachusetts en 1979. Es muy conocido por su trabajo en la computación aleatoria, en la complejidad de los algorítmicos, en los fundamentos de las matemáticas e informática, en la teoría del cómputo y en la teoría de la información. (es) Leonid Anatolievich Levin (/leɪ.oʊˈniːd ˈlɛvɪn/ lay-oh-NEED LEV-in; Russian: Леони́д Анато́льевич Ле́вин; Ukrainian: Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American mathematician and computer scientist. Levin was awarded the Knuth Prize in 2012 for his discovery of NP-completeness and the development of average-case complexity.He is a member of the US National Academy of Sciences anda fellow of the American Academy of Arts and Sciences. (en) Leonid Anatolievich Levin, em russo: Леонид Анатольевич Левин; (Dnipropetrovsk, 2 de novembro de 1948) é um informático soviético-estadunidense. Obteve o mestrado em 1970 e um Ph.D. em 1972 na Universidade de Moscou, onde foi aluno de Andrey Kolmogorov. Em 1978 emigrou para os Estados Unidos, obtendo um Ph.D. no Instituto de Tecnologia de Massachusetts (MIT) em 1979. Seu orientador no MIT foi Albert Ronald Meyer. Atualmente é professor de ciência da computação na Universidade de Boston, onde começou a lecionar em 1980. (pt) |
| rdfs:label | Leonid Levin (en) Leonid Levin (de) Leonid Levin (es) Leonid Levin (fr) 레오니드 레빈 (ko) Левин, Леонид Анатольевич (ru) Leonid Levin (pt) Левін Леонід Анатолійович (uk) |
| owl:sameAs | freebase:Leonid Levin http://data.europa.eu/euodp/jrc-names/Leonid_Levin http://viaf.org/viaf/70440154 yago-res:Leonid Levin https://dblp.org/pid/l/LeonidALevin wikidata:Leonid Levin http://arz.dbpedia.org/resource/ليونيد_ليڤين dbpedia-de:Leonid Levin dbpedia-es:Leonid Levin dbpedia-fa:Leonid Levin dbpedia-fr:Leonid Levin http://ht.dbpedia.org/resource/Leonid_Levin dbpedia-ko:Leonid Levin dbpedia-pt:Leonid Levin dbpedia-ru:Leonid Levin dbpedia-sk:Leonid Levin dbpedia-th:Leonid Levin dbpedia-uk:Leonid Levin https://global.dbpedia.org/id/558Y9 |
| prov:wasDerivedFrom | wikipedia-en:Leonid_Levin?oldid=1059602690&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/LeonidLevin2010.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Leonid_Levin |
| foaf:name | Leonid Anatolievich Levin (en) |
| is dbo:doctoralStudent of | dbr:Andrey_Kolmogorov dbr:Albert_R._Meyer |
| is dbo:wikiPageDisambiguates of | dbr:Leonid |
| is dbo:wikiPageRedirects of | dbr:Леони́д_Анато́льевич_Ле́вин dbr:L._A._Levin dbr:Leonid_A._Levin dbr:Leonid_Anatolievich_Levin |
| is dbo:wikiPageWikiLink of | dbr:Science_and_technology_in_Ukraine dbr:List_of_Ukrainian_Jews dbr:List_of_computer_scientists dbr:MSU_Faculty_of_Mechanics_and_Mathematics dbr:Algorithmic_information_theory dbr:Algorithmic_probability dbr:History_of_the_Jews_in_Russia dbr:List_of_important_publications_in_theoretical_computer_science dbr:Peter_Gacs dbr:Levin_(surname) dbr:List_of_multiple_discoveries dbr:List_of_people_by_Erdős_number dbr:Cook–Levin_theorem dbr:Andrey_Kolmogorov dbr:Stephen_Cook dbr:Computational_complexity_theory dbr:Leonid dbr:Majority_problem_(cellular_automaton) dbr:Theoretical_computer_science dbr:Jewish_Ukrainian_mathematicians dbr:List_of_Boston_University_people dbr:Albert_R._Meyer dbr:Algorithmically_random_sequence dbr:Hard-core_predicate dbr:Kolmogorov_Medal dbr:Kolmogorov_complexity dbr:Leftover_hash_lemma dbr:List_of_Guggenheim_Fellowships_awarded_in_1993 dbr:List_of_International_Congresses_of_Mathematicians_Plenary_and_Invited_Speakers dbr:List_of_Jewish_American_computer_scientists dbr:List_of_Jewish_mathematicians dbr:List_of_Jews_born_in_the_Russian_Empire_and_the_Soviet_Union dbr:List_of_Moscow_State_University_people dbr:List_of_Russian_IT_developers dbr:List_of_Russian_mathematicians dbr:List_of_Russian_scientists dbr:Gregory_Chaitin dbr:Lance_Fortnow dbr:Dnipro dbr:Average-case_complexity dbr:Boolean_satisfiability_problem dbr:Humboldt_Prize dbr:P_versus_NP_problem dbr:Леони́д_Анато́льевич_Ле́вин dbr:Random_sequence dbr:L._A._Levin dbr:Leonid_A._Levin dbr:Leonid_Anatolievich_Levin |
| is dbp:doctoralStudents of | dbr:Albert_R._Meyer |
| is foaf:primaryTopic of | wikipedia-en:Leonid_Levin |
