U.S. flag
        An official website of the United States government
          Here’s how you know
        Here’s how you know**Official websites use .gov**
              
              A **.gov** website belongs to an official government organization in the United States.
        **Secure .gov websites use HTTPS**
              
              A **lock** (  A locked padlock
) or **https://** means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites. https://www.nist.gov/mathematics-statistics/first-mathematical-theory-efficient-combinatorial-algorithms-jack-edmonds
  Search NIST
    Search
              Menu

      


Close
    Topics
        All Topics
                                                        Advanced communications
                                                        Artificial intelligence
                                                        Bioscience
                                                        Buildings and construction
                                                        Chemistry
                                                        Climate
                                                        Cybersecurity
                                                        Electronics
                                                        EnergyEnvironment
                                                        Fire
                                                        Forensic science
                                                        Health
                                                        Information technology
                                                        Infrastructure
                                                        Manufacturing
                                                        Materials
                                                        Mathematics and statisticsMetrology
                                                        Nanotechnology
                                                        Neutron research
                                                        Performance excellence
                                                        Physics
                                                        Public safety
                                                        Resilience
                                                        Standards
                                                        Transportation
            Publications
            Labs & Major Programs
        Laboratories
                                Communications Technology Laboratory
                                  Engineering Laboratory
                                  Information Technology Laboratory
                                  Material Measurement Laboratory
                                  Physical Measurement LaboratoryUser Facilities
                                NIST Center for Neutron Research
                                  CNST NanoFab
                                                        Research Test Beds
                                                        Research Projects
                                                        Tools & InstrumentsMajor Programs
                                Baldrige Performance Excellence Program
                                  CHIPS for America Initiative
                                  Manufacturing Extension Partnership (MEP)
                                  Office of Advanced Manufacturing
                                  Special Programs Office
                                  Technology Partnerships Office
            Services & Resources
        Standards and Measurements
                                Calibration Services
                                  Laboratory Accreditation (NVLAP)
                                  Quality System
                                  Standard Reference Materials (SRMs)
                                  Standards.gov
                                  Time Services
                                  Office of Weights and MeasuresSoftware
                                                        Data
                                Chemistry WebBook
                                  National Vulnerability Database
                                  Physical Reference Data
                                  Standard Reference Data (SRD)
                                                        Storefront
                                                        License & PatentsComputer Security Resource Center (CSRC)
                                                        NIST Research Library
            News & Events
        News
                                                        Events
                                                        Blogs
                                                        Feature Stories
                                                        AwardsVideo Gallery
                                                        Image Gallery
                                                        Media Contacts
            About NIST
        About Us
                                Leadership
                                  Organization Structure
                                  Budget & Planning
                                                        Contact Us
                                                        Visit
                                                        Careers
                                Student programsWork with NIST
                                                        History
                                NIST Digital Archives
                                  NIST Museum
                                  NIST and the Nobel
                                                        Educational Resources
 
 Mathematics & Statistics
    
      
  First Mathematical Theory of Efficient Combinatorial Algorithms: Jack Edmonds

Share
  Facebook
                      Linkedin
                      Twitter
                      Email

**Date: 1965**

*One of the creators of the fields of combinatorial optimization, polyhedral combinatorics, and computational complexity theory, NIST’s Jack Edmonds helped identify what is perhaps the most sought-after question in computer science research today: Is P=NP?*

      Image: Jack Edmonds
Jack EdmondsCredit:
          
  NISTJack Edmonds is widely acknowledged as one of the creators of the fields of combinatorial optimization and polyhedral combinatorics, which emerged during the period of Edmond’s tenure at NBS (1959-69). Combinatorial optimization is the process of identifying the “best” from a finite (but often very large) set of choices. A classic example is the well-known travelling salesman problem. Polyhedral combinatorics studies the relationship between counting problems and geometric objects, thus enabling geometrical reasoning to be applied the solution of challenging counting and optimization problems. The foundation of modern operations research, combinatorial optimization is routinely used today in such areas as vehicle routing, class scheduling, bin packing, and target assignment.

In recognition for his contributions to this field, Edmonds was awarded the prestigious John von Neumann Theory Prize by The Institute for Operations Research and the Management Sciences[1](INFORMS) in 1985. In the citation for that award, two of Edmonds’ NBS publications are explicitly mentioned [1, 2]:

“His 1965 paper *Paths, Trees, and Flowers* was one of the first papers to suggest the possibility of establishing a mathematical theory of efficient combinatorial algorithms. In that paper and in the subsequent paper *Maximum Matching and a Polyhedron with 0-1 Vertices* Edmonds gave remarkable polynomial-time algorithms for the construction of maximum matchings. Even more importantly these papers showed how a good characterization of the polyhedron associated with a combinatorial optimization problem could lead via the duality theory of linear programming, to the construction of an efficient algorithm for the solution of that problem.”

Edmonds’ work at NBS also laid foundations for the newly emerging field of computer science. In fact, his early work led to the characterization of one of today’s most important open questions in the theory of computation. As demonstrated by its inclusion as one of the Clay Mathematics Institute’s Millennial Problems[2], a central question in theoretical computer science is whether or not the class of problems whose solutions can be *verified* in time that grows like a polynomial in the size of the input (“NP”) is the same as the class of problems whose solutions can be *computed* in polynomial time (“P”).  In a series of papers published while at NBS [4], he was the first to describe the complexity class NP, to describe a tractable computation as one that is solvable in polynomial time, and to state the now widely held conjecture that the complexity classes P and NP are not equivalent.  In other words, much of modern computational complexity theory originates from Edmonds' work while at NBS.

References

Jack Edmonds, Paths, Trees, and Flowers, Canad. J. Math. 17, 449-467 (1965).
	Jack Edmonds, Covers and Packings in a Family of Sets, Bull. Amer. Math. Soc. 68, 494-499 (1962).
	Jack Edmonds, Existence of k-Edge Connected Ordinary Graphs with Prescribed Degrees, J. Res. Natl. Bur. Stand. 68B, 73-74 (1964).
	Jack Edmonds, Minimum Partition of a Matroid into Independent Subsets, J. Res. Natl. Bur. Stand. 69B, 67-72 (1965).
	C. Witzgall. Paths, Trees and Flowers.In *A Century of Excellence in Measurements, Standards, and Technology* (D. R. Lide, ed.), NIST Special Publication 958, 2001.https://nvlpubs.nist.gov/nistpubs/sp958-lide/140-144.pdf

[1] http://informs.org/

[2] http://www.claymath.org/millennium/
  Information technology and Mathematics and statistics

    
    Created March 14, 2022, Updated April 21, 2022
 HEADQUARTERS
            100 Bureau Drive
              Gaithersburg, MD 20899301-975-2000
            Webmaster | Contact Us | Our Other Offices
        Twitter
            
Facebook
            
LinkedIn
            
Instagram
            
YouTube
            
Giphy
            
RSS Feed
            
Mailing List
                              How are we doing? Feedback

  
  Site Privacy
                      Accessibility
                      Privacy Program
                      Copyrights
                      Vulnerability Disclosure
                      No Fear Act Policy
                      FOIA
                      Environmental Policy
                      Scientific Integrity
                      Information Quality Standards
                      Commerce.gov
                      Science.gov
                      USA.gov
                      Vote.gov