* . *
  • About
  • Advertise
  • Privacy & Policy
  • Contact
Sunday, August 3, 2025
Earth-News
  • Home
  • Business
  • Entertainment
    Chicago Youth Symphony Orchestra takes the Lollapalooza stage – Yahoo Home

    Chicago Youth Symphony Orchestra takes the Lollapalooza stage – Yahoo Home

    Sens. Blackburn, Warnock introduce CREATE Act to provide tax relief to music creators – Yahoo Home

    Sens. Blackburn and Warnock Launch CREATE Act to Deliver Tax Relief for Music Creators

    That’s (Political) Entertainment: When Theatre Meets Politics

    Future Script: How Generative AI Is Changing Collective Bargaining in the Entertainment Industry – Jackson Lewis

    Future Script: How Generative AI Is Transforming Collective Bargaining in Entertainment

    The SBA’s live-entertainment bailout was supposed to end two years ago. We still don’t know how $1.5 billion was spent. – Yahoo Home

    $1.5 Billion Live-Entertainment Bailout: Two Years Later, Where Did the Money Go?

    Wall Street Bets: Caesars, Golden Entertainment, Churchill Downs, GLPI, Boyd – CDC Gaming

    Top Wall Street Bets: Caesars, Golden Entertainment, Churchill Downs, GLPI, and Boyd Take Center Stage

  • General
  • Health
  • News

    Cracking the Code: Why China’s Economic Challenges Aren’t Shaking Markets, Unlike America’s” – Bloomberg

    Trump’s Narrow Window to Spread the Truth About Harris

    Trump’s Narrow Window to Spread the Truth About Harris

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Trending Tags

    • Trump Inauguration
    • United Stated
    • White House
    • Market Stories
    • Election Results
  • Science
  • Sports
  • Technology
    Livonia police use grappler technology to stop drunk driver – ClickOnDetroit | WDIV Local 4

    Livonia Police Deploy Grappler Technology to Safely Stop Drunk Driver

    Emory orthopaedic surgeons use robotic technology to transform knee replacement surgery – Emory News Center

    How Robotic Technology is Revolutionizing Knee Replacement Surgery

    Cognizant Technology Solutions Corp (CTSH) Q2 2025 Earnings Call Highlights: Strong Revenue … – Yahoo.co

    Cognizant Q2 2025 Earnings: Impressive Revenue Growth and Key Takeaways

    Revving Up The U.S. Technology Engine – Forbes

    Revving Up The U.S. Technology Engine – Forbes

    More than just a hockey player – Rochester Institute of Technology Athletics

    Beyond the Ice: The Inspiring Journey of a Remarkable Athlete from Rochester Institute of Technology

    Smart Logistics in Warehousing – From Legacy Protocols to Green IoT – How Technology Is Reshaping the Sustainable Supply Chain – Logistics Viewpoints –

    Smart Logistics in Warehousing – From Legacy Protocols to Green IoT – How Technology Is Reshaping the Sustainable Supply Chain – Logistics Viewpoints –

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
  • Home
  • Business
  • Entertainment
    Chicago Youth Symphony Orchestra takes the Lollapalooza stage – Yahoo Home

    Chicago Youth Symphony Orchestra takes the Lollapalooza stage – Yahoo Home

    Sens. Blackburn, Warnock introduce CREATE Act to provide tax relief to music creators – Yahoo Home

    Sens. Blackburn and Warnock Launch CREATE Act to Deliver Tax Relief for Music Creators

    That’s (Political) Entertainment: When Theatre Meets Politics

    Future Script: How Generative AI Is Changing Collective Bargaining in the Entertainment Industry – Jackson Lewis

    Future Script: How Generative AI Is Transforming Collective Bargaining in Entertainment

    The SBA’s live-entertainment bailout was supposed to end two years ago. We still don’t know how $1.5 billion was spent. – Yahoo Home

    $1.5 Billion Live-Entertainment Bailout: Two Years Later, Where Did the Money Go?

    Wall Street Bets: Caesars, Golden Entertainment, Churchill Downs, GLPI, Boyd – CDC Gaming

    Top Wall Street Bets: Caesars, Golden Entertainment, Churchill Downs, GLPI, and Boyd Take Center Stage

  • General
  • Health
  • News

    Cracking the Code: Why China’s Economic Challenges Aren’t Shaking Markets, Unlike America’s” – Bloomberg

    Trump’s Narrow Window to Spread the Truth About Harris

    Trump’s Narrow Window to Spread the Truth About Harris

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Trending Tags

    • Trump Inauguration
    • United Stated
    • White House
    • Market Stories
    • Election Results
  • Science
  • Sports
  • Technology
    Livonia police use grappler technology to stop drunk driver – ClickOnDetroit | WDIV Local 4

    Livonia Police Deploy Grappler Technology to Safely Stop Drunk Driver

    Emory orthopaedic surgeons use robotic technology to transform knee replacement surgery – Emory News Center

    How Robotic Technology is Revolutionizing Knee Replacement Surgery

    Cognizant Technology Solutions Corp (CTSH) Q2 2025 Earnings Call Highlights: Strong Revenue … – Yahoo.co

    Cognizant Q2 2025 Earnings: Impressive Revenue Growth and Key Takeaways

    Revving Up The U.S. Technology Engine – Forbes

    Revving Up The U.S. Technology Engine – Forbes

    More than just a hockey player – Rochester Institute of Technology Athletics

    Beyond the Ice: The Inspiring Journey of a Remarkable Athlete from Rochester Institute of Technology

    Smart Logistics in Warehousing – From Legacy Protocols to Green IoT – How Technology Is Reshaping the Sustainable Supply Chain – Logistics Viewpoints –

    Smart Logistics in Warehousing – From Legacy Protocols to Green IoT – How Technology Is Reshaping the Sustainable Supply Chain – Logistics Viewpoints –

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
Earth-News
No Result
View All Result
Home Science

The Most Important Unsolved Problem in Computer Science

December 22, 2023
in Science
The Most Important Unsolved Problem in Computer Science
Share on FacebookShare on Twitter

When the Clay Mathematics Institute put individual $1-million prize bounties on seven unsolved mathematical problems, they may have undervalued one entry—by a lot. If mathematicians were to resolve, in the right way, computer science’s “P versus NP” question, the result could be worth worlds more than $1 million—they’d be cracking most online-security systems, revolutionizing science and even mechanistically solving the other six of the so-called Millennium Problems, all of which were chosen in the year 2000. It’s hard to overstate the stakes surrounding the most important unsolved problem in computer science.

P versus NP concerns the apparent asymmetry between finding solutions to problems and verifying solutions to problems. For example, imagine you’re planning a world tour to promote your new book. You pull up Priceline and start testing routes, but each one you try blows your total trip budget. Unfortunately, as the number of cities grows on your worldwide tour, the number of possible routes to check skyrockets exponentially, rapidly making it infeasible even for computers to exhaustively search through every case. But when you complain, your agent writes back with a solution sequence of flights. You can easily verify whether or not their route stays in budget by simply checking that it hits every city and summing the fares to compare against the budget limit. Notice the asymmetry here: finding a solution is hard, but verifying a solution is easy.

The P versus NP question asks whether this asymmetry is real or an illusion. If you can efficiently verify a solution to a problem, does that imply that you can also efficiently find a solution? Perhaps a clever shortcut can circumvent searching through zillions of potential routes. For example, if your agent instead wanted you to find a sequence of flights between two specific remote airports while obeying the budget, you might also throw up your hands at the similarly immense number of possible routes to check, but in fact, this problem contains enough structure that computer scientists have developed a fast procedure (algorithm) for it that bypasses the need for exhaustive search.

You might think this asymmetry is obvious: of course one would sometimes have a harder time finding a solution to a problem than verifying it. But researchers have been surprised before in thinking that that’s the case, only to discover last-minute that the solution is just as easy. So every attempt in which they try to resolve this question for any single scenario only further exposes how monumentally difficult it is to prove one way or another. P versus NP also rears its head everywhere we look in the computational world well beyond the specifics of our travel scenario—so much so that it has come to symbolize a holy grail in our understanding of computation.

In the subfield of theoretical computer science called complexity theory, researchers try to pin down how easily computers can solve various types of problems. P represents the class of problems they can solve efficiently, such as sorting a column of numbers in a spreadsheet or finding the shortest path between two addresses on a map. NP represents the class of problems for which computers can verify solutions efficiently. Our book tour problem, called the Traveling Salesperson Problem by academics, lives in NP because we have an efficient procedure for verifying that our agent’s solution worked.

Notice that NP actually contains P as a subset because solving a problem outright is one way to verify a solution to it. For example, how would you verify that 27 x 89=2,403? You would solve the multiplication problem yourself and check that your answer matches the claimed one. We typically depict the relationship between P and NP with a simple Venn diagram:

Venn diagram shows one large circle labeled “NP” encompassing a smaller one labeled “P.” The entire circle is labeled “Problems with solutions that computers can verify easily.” The area inside of P is labeled “Problems with solutions that computers can find easily.” The area in NP but outside of P is labeled “Problems with solutions that computers can verify but not find easily.”
Credit: Amanda Montañez

The region inside of NP but not inside of P contains problems that can’t be solved with any known efficient algorithm. (Theoretical computer scientists use a technical definition for “efficient” that can be debated, but it serves as a useful proxy for the colloquial concept.) But we don’t know if that’s because such algorithms don’t exist or we just haven’t mustered the ingenuity to discover them. Here’s another way to phrase the P versus NP question: Are these classes actually distinct? Or does the Venn diagram collapse into one circle? Do all NP problems admit efficient algorithms? Here are some examples of problems in NP that are not currently known to be in P:

Given a social network, is there a group of a specified size in which all of the people in it are friends with one another?
Given a varied collection of boxes to be shipped, can all of them be fit into a specified number of trucks?
Given a sudoku (generalized to n x n puzzle grids), does it have a solution?
Given a map, can the countries be colored with only three colors such that no two neighboring countries are the same color?

Ask yourself how you would verify proposed solutions to some of the problems above and then how you would find a solution. Note that approximating a solution or solving a small instance (most of us can solve a 9 x 9 sudoku) doesn’t suffice. To qualify as solving a problem, an algorithm needs to find an exact solution on all instances, including very large ones.

Each of the problems can be solved via brute-force search (e.g., try every possible coloring of the map and check if any of them work), but the number of cases to try grows exponentially with the size of the problem. This means that if we call the size of the problem n (e.g., the number of countries on the map or the number of boxes to pack into trucks), then the number of cases to check looks something like 2n. The world’s fastest supercomputers have no hope against exponential growth. Even when n equals 300, a tiny input size by modern data standards, 2300 exceeds the number of atoms in the observable universe. After hitting “go” on such an algorithm, your computer would display a spinning pinwheel that would outlive you and your descendants.

Thousands of other problems belong on our list. From cell biology to game theory, the P versus NP question reaches into far corners of science and industry. If P=NP (i.e., our Venn diagram dissolves into a single circle) and we obtain fast algorithms for these seemingly hard problems, then the whole digital economy would become vulnerable to collapse. This is because much of the cryptography that secures such things as your credit card number and passwords works by shrouding private information behind computationally difficult problems that can only become easy to solve if you know the secret key. Online security as we know it rests on unproven mathematical assumptions that crumble if P=NP.

Amazingly, we can even cast math itself as an NP problem because we can program computers to efficiently verify proofs. In fact, legendary mathematician Kurt Gödel first posed the P versus NP problem in a letter to his colleague John von Neumann in 1956, and he expressed (in older terminology) that P=NP “would have consequences of the greatest importance. Namely, it would obviously mean that … the mental work of a mathematician concerning yes-or-no questions could be completely replaced by a machine.”

If you’re a mathematician worried for your job, rest assured that most experts believe that P does not equal NP. Aside from the intuition that sometimes solutions should be harder to find than to verify, thousands of the hardest NP problems that are not known to be in P have sat unsolved across disparate fields, glowing with incentives of fame and fortune, and yet not one person has designed an efficient algorithm for a single one of them.

Of course, gut feeling and a lack of counterexamples don’t constitute a proof. To prove that P is different from NP, you somehow have to rule out all potential algorithms for all of the hardest NP problems, a task that appears out of reach for current mathematical techniques. In fact, the field has coped by proving so-called barrier theorems, which say that entire categories of tempting proof strategies to resolve P versus NP cannot succeed. Not only have we failed to find a proof but we also have no clue what an eventual proof might look like.

>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Scientific American – https://www.scientificamerican.com/article/the-most-important-unsolved-problem-in-computer-science/

Tags: importantscienceUnsolved
Previous Post

Brandline Recalls HEAO High Chairs Due to Risk of Suffocation, Entrapment and Laceration Hazards; Violation of the Federal Safety Standards; Sold Exclusively on Amazon.com

Next Post

You Can Literally Sniff Out Other People’s Inner Feelings

Endemism shapes viral ecology and evolution in globally distributed hydrothermal vent ecosystems – Nature

Endemism shapes viral ecology and evolution in globally distributed hydrothermal vent ecosystems – Nature

August 2, 2025
Scientists Finally Reveal the Hidden Trigger Behind Lightning Strikes

Scientists Finally Reveal the Hidden Trigger Behind Lightning Strikes

August 2, 2025
Young minds explore science at NDSU summer research program – InForum

Young Minds Ignite Curiosity at NDSU Summer Science Research Program

August 2, 2025
PlayStation Preparing to Release More Games on Xbox – Report – PlayStation LifeStyle

PlayStation Gears Up to Launch Exciting New Games on Xbox

August 2, 2025
Lexington County hits a home run hosting the Diamond Youth Baseball World Series – WLTX

Lexington County Hits a Home Run Hosting the Diamond Youth Baseball World Series

August 2, 2025
Some rural Texans see THC as a lifeline for their health and economy – The Texas Tribune

How THC Is Revolutionizing Health and Sparking Economic Growth in Rural Texas

August 2, 2025
Fox Corporation Acquires One-Third Interest in Penske Entertainment – INDYCAR.com

Fox Corporation Makes Bold Move with Major Investment in Penske Entertainment, Powering INDYCAR’s Future

August 2, 2025
Minnesotans face health impacts as wildfire smoke lingers – kare11.com

Minnesotans face health impacts as wildfire smoke lingers – kare11.com

August 2, 2025
Trump announces sweeping new levies for scores of countries – as it happened – The Guardian

Trump announces sweeping new levies for scores of countries – as it happened – The Guardian

August 2, 2025
Livonia police use grappler technology to stop drunk driver – ClickOnDetroit | WDIV Local 4

Livonia Police Deploy Grappler Technology to Safely Stop Drunk Driver

August 2, 2025

Categories

Archives

August 2025
MTWTFSS
 123
45678910
11121314151617
18192021222324
25262728293031
« Jul    
Earth-News.info

The Earth News is an independent English-language daily published Website from all around the World News

Browse by Category

  • Business (20,132)
  • Ecology (751)
  • Economy (776)
  • Entertainment (21,653)
  • General (16,252)
  • Health (9,813)
  • Lifestyle (784)
  • News (22,149)
  • People (776)
  • Politics (785)
  • Science (15,989)
  • Sports (21,271)
  • Technology (15,753)
  • World (758)

Recent News

Endemism shapes viral ecology and evolution in globally distributed hydrothermal vent ecosystems – Nature

Endemism shapes viral ecology and evolution in globally distributed hydrothermal vent ecosystems – Nature

August 2, 2025
Scientists Finally Reveal the Hidden Trigger Behind Lightning Strikes

Scientists Finally Reveal the Hidden Trigger Behind Lightning Strikes

August 2, 2025
  • About
  • Advertise
  • Privacy & Policy
  • Contact

© 2023 earth-news.info

No Result
View All Result

© 2023 earth-news.info

No Result
View All Result

© 2023 earth-news.info

Go to mobile version