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?


closed as off-topic by D.W., Aryeh, Kaveh, Emil Jeřábek, 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, 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