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?

  • 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