1
$\begingroup$

Looking at this wiki page, 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?

$\endgroup$

closed as off-topic by D.W., Aryeh, Kaveh, Emil Jeřábek supports Monica, Bruno Feb 11 '18 at 18:14

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – D.W., Aryeh, Kaveh, Emil Jeřábek supports Monica, Bruno
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ 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 (which became a book in 2000) ... $\endgroup$ – Marzio De Biasi Feb 7 '18 at 11:22
  • 3
    $\begingroup$ ... A simple problem example is: "Is the Mandelbrot set decidable?" (there are several nonequivalent computability notions over the real or complex numbers, so the answer may be positive in one model, negative in another) $\endgroup$ – Marzio De Biasi Feb 7 '18 at 11:38
  • 1
    $\begingroup$ See Ker-I Ko's book/papers on complexity theory of real fictions. $\endgroup$ – Kaveh Feb 7 '18 at 12:33
  • $\begingroup$ @Kaveh, in the spirit of Borges and Lem? $\endgroup$ – András Salamon Feb 11 '18 at 12:05
  • 1
    $\begingroup$ @Kaveh: just riffing on your "real fictions"... $\endgroup$ – András Salamon Feb 12 '18 at 14:46