Groups > comp.programming.threads > #5062

Race condition detection is NP-hard

From	Horizon68 <horizon@horizon.com>
Newsgroups	comp.programming.threads
Subject	Race condition detection is NP-hard
Date	2019-06-29 12:19 -0700
Organization	A noiseless patient Spider
Message-ID	<qf8dk5$tlj$4@dont-email.me> (permalink)

Show all headers | View raw

Hello..


NP-hard problem means there is no known algorithm can solve it in a 
polynomial time, so that the time to find a solution grows exponentially 
with problem size. Although it has not been definitively proven that, 
there is no polynomial algorithm for solving NP-hard problems, many 
eminent mathematicians have tried and failed.

Race condition detection is NP-hard

Read more here:

https://pages.mtu.edu/~shene/NSF-3/e-Book/RACE/difficult.html



Thank you,
Amine Moulay Ramdane.

Back to comp.programming.threads | Previous | Next | Find similar | Unroll thread

Thread

Race condition detection is NP-hard Horizon68 <horizon@horizon.com> - 2019-06-29 12:19 -0700

csiph-web