<p>Looking at this <a href="https://en.wikipedia.org/wiki/List_of_NP-complete_problems" rel="nofollow noreferrer">wiki page</a>, it seems most NP-complete problems are based on discrete structures, such as graphs. What are some problems that involve real or complex analysis instead of discrete analysis? If none, why not?</p>

CC BY-SA 3.0
2018-02-07T11:22:41.333Z
I'm not an expert but I think that (i) problems on discrete structures are often real everyday problems (e.g. TSP, knapsack, ...) so they often have real-life applications (ii) there are enough troubles with discrete structures and switching to real analysis often means dealing not only with "hardness" but also with "uncomputability" . BTW there is surely some research on the topic; see for example [A simple introduction to computable analysis](https://eccc.weizmann.ac.il/resources/pdf/ica.pdf) (which became a [book](http://www.springer.com/us/book/9783540668176) in 2000) ...
Marzio De Biasi
CC BY-SA 3.0
2018-02-07T11:38:04.850Z
... A simple problem example is: "[Is the Mandelbrot set decidable?](http://www.netbased-university.de/imperia/md/content/fakultaetfuermathematikundinformatik/forschung/berichte/bericht_298.pdf)" (there are several nonequivalent computability notions over the real or complex numbers, so the answer may be positive in one model, negative in another)
Marzio De Biasi
CC BY-SA 3.0
2018-02-07T12:33:57.710Z
See Ker-I Ko's book/papers on complexity theory of real fictions.
Kaveh
CC BY-SA 3.0
2018-02-11T12:05:20.300Z
@Kaveh, in the spirit of Borges and Lem?
András Salamon
CC BY-SA 3.0
2018-02-11T13:21:59.867Z
@András, not familiar with that. I am referring e.g. to this book: https://books.google.ca/books?id=QJnVBwAAQBAJ
Kaveh
CC BY-SA 3.0
2018-02-12T14:46:17.810Z
@Kaveh: just riffing on your "real fictions"...
András Salamon
<np-hardness><np-complete>
Are there any NP-complete for continuous mathematics?
Joseph
# Are there any NP-complete for continuous mathematics?

(Asked by: username_0 on 2018-02-07)

Looking at this [wiki page](https://en.wikipedia.org/wiki/List_of_NP-complete_problems), it seems most NP-complete problems are based on discrete structures, such as graphs. What are some problems that involve real or complex analysis instead of discrete analysis? If none, why not?

**Tags:** np-hardness, np-complete

> **Comments:**
> **username_1**: I'm not an expert but I think that (i) problems on discrete structures are often real everyday problems (e.g. TSP, knapsack, ...) so they often have real-life applications (ii) there are enough troubles with discrete structures and switching to real analysis often means dealing not only with "hardness" but also with "uncomputability" . BTW there is surely some research on the topic; see for example [A simple introduction to computable analysis](https://eccc.weizmann.ac.il/resources/pdf/ica.pdf) (which became a [book](http://www.springer.com/us/book/9783540668176) in 2000) ...  
> **username_1**: ... A simple problem example is: "[Is the Mandelbrot set decidable?](http://www.netbased-university.de/imperia/md/content/fakultaetfuermathematikundinformatik/forschung/berichte/bericht_298.pdf)" (there are several nonequivalent computability notions over the real or complex numbers, so the answer may be positive in one model, negative in another)  
> **username_2**: See Ker-I Ko's book/papers on complexity theory of real fictions.  
> **username_3**: @username_2, in the spirit of Borges and Lem?  
> **username_2**: @András, not familiar with that. I am referring e.g. to this book: https://books.google.ca/books?id=QJnVBwAAQBAJ  
> **username_3**: @username_2: just riffing on your "real fictions"...  

---

## 0 answers

