0
$\begingroup$

I'm writing paper and need your help in finding some famous (or not so famous) problems without efficient algorithm, but from logic or computer science. So far, I have:

-Boolean satisfiability problem

-decision problem that asks whether a certain string s belongs to the language of a certain context-sensitive grammar G (its PSPACE-complete)

-problem whether a regular expression with exponentiation denotes all strings over its alphabet (exponential time)

Are there any other more or less famous problems that I could put in paper and write about?

$\endgroup$
1
$\begingroup$

Some examples:

  • You could start with any well-known NP-hard problem (that includes NP-complete problems too, as well as PSPACE-complete, etc.).
  • Many equivalence-related algorithms for automatons and logic formulas, for example
  • Some type inference algorithms, e.g. for rank-2 types (ranks 3 or higher are undecidable) or for kind-2 types (kinds 3 or higher are also undecidable).
  • Many games, like go, lead to hard problems, try this search.

I hope this helps $\ddot\smile$

$\endgroup$
1
$\begingroup$

Oh, there are plenty of famous and important NP-hard problems. Here's the first list from a Google search. IMO the most important ones in practical applications are Bin Packing, Travelling Salesman, and Integer Programming problems, although many other ones are important as well.

$\endgroup$
0
$\begingroup$

Sorting. Any sorting on a list of $n$ elements is a polynomial problem.

$\endgroup$
  • 1
    $\begingroup$ He's asking for problems for which there do not exist polynomial-time algorithms. $\endgroup$ – Aleš Bizjak Jan 9 '14 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.