Questions with a broad scope about general methods and concepts, such as proof-methods, tools for algorithm analysis or basics of computer architecture. This is *not* for questions asking *for* references, i.e. books or articles.
9
votes
1answer
106 views
How to formulate a computational problem rigorously?
I often interact with people who want to ask for an algorithm for a computational problem (or its complexity), but they don't express it in a rigorous way for us (computer scientists) to understand.
...
3
votes
1answer
86 views
How to show that L = L(G)?
Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...
14
votes
3answers
224 views
What are common techniques for reducing problems to each other?
In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as ...
4
votes
1answer
129 views
How to show that a function is not computable?
I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
25
votes
3answers
903 views
In basic terms, what is the definition of P, NP, NP-Complete, and NP-Hard?
I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that np is a subset of np complete which is a subset of np hard... but I have no idea ...
14
votes
7answers
1k views
How does the computer determine whether a number is smaller or greater than another?
It might sound like a stupid question but I'm really curious to know how a computer knows that $1<2$? Also, how does a computer know that the order of integer is $1,2,3,4,5,\ldots$ and alphabet is ...
14
votes
5answers
683 views
How does a computer work?
Ok, I have been a computer nerd for many many years. I can program in quite a few languages, and I can even build them. I sat down with a buddy the other day and asked how a computer actually takes ...
23
votes
7answers
738 views
Solving or approximating recurrence relations for sequences of numbers
In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
13
votes
4answers
5k views
How to convert finite automata to regular expressions?
Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms. The other direction seems to be more tedious, though, and sometimes the resulting ...
29
votes
5answers
5k views
How not to solve P=NP?
There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either ...
25
votes
6answers
681 views
How can we assume comparison, addition, … between numbers is $O(1)$
Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they are $O(1)$. For example we assume this when we say that comparison based sorting is ...
16
votes
6answers
441 views
Dealing with intractability: NP-complete problems
Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?
11
votes
4answers
2k views
How to prove a language is regular?
There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular?
For instance, if I am given that $L$ is regular,
how can I prove that ...
20
votes
5answers
5k views
How to prove that a language is not regular?
We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
6
votes
5answers
370 views
Sorting functions by asymptotic growth
Assume I have a list of functions, for example
$\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots$
How do I sort them asymptotically, i.e. after the relation defined by
$\qquad f \leq_O g ...
