# Questions tagged [reference-question]

Reserved -- shouldn't be used for most new questions. 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.

30 questions
Filter by
Sorted by
Tagged with
58 views

### If X is polynomial-time reducible to Y and X is polynomial-time reducible to Z then Y is polynomial-time reducible to Z?

If $X$ is polynomial-time reducible to $Y$ and $X$ is polynomial-time reducible to $Z$, $Y$ is polynomial-time reducible to $Z$? If $X \leq_p Y$ and $X \leq_p Z$ then $Y \leq_p Z$? True, false or we ...
39 views

### If X is in NP then $\overline{X}$ is in NP. True, false or “we don't know”? Why?

If X is in NP then $\overline{X}$ is in NP. True, false or "we don't know"? Why?
77 views

### If X is polynomial reduction to Y and Y is in NP, then X is in NP? [duplicate]

If X is polynomial reduction to Y and Y is in NP, then X is in NP? Is this true, false or "we don't know"? Why?
38 views

### Computing the partition function

Are there in any relatively efficient known algorithms to compute the partition function $P(n)$ for a given $n$? What's known about the complexity class of this problem as a function of $n$? ...
587 views

### What does the “big O complexity” of a function mean?

What do people mean when they refer to the "big O complexity" of a function? What is the big O complexity of $9n^2 + 10n$, for example?
616 views

### Why nondeterminism?

Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and ...
2k views

### What's wrong with my pumping lemma proof?

The language $L = \{0^{2n} \space |\space n \ge 0 \}$ is obviously regular – for example, it matches the regular expression $(00)^*$. But the following pumping lemma argument seems to show it's ...
20k views

### Is there a system behind the magic of algorithm analysis?

There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...
53k views

### How do O and Ω relate to worst and best case?

Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements. ...
32k views

### How to prove that a language is context-free?

There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free? What techniques are there to prove this? Obviously, one way is to exhibit ...
7k views

### What is the difference between an algorithm, a language and a problem?

It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
7k 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 ...
15k 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 ...
17k 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 ...
133k views

### 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 ...
22k 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 ...
15k views

### How do I write a proof using induction on the length of the input string?

In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however ...
5k views

### How does a computer work?

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 ...
21k 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 ...
177k 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, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
16k 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 direction....
18k views

### How can we assume that basic operations on numbers take constant time?

Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$. For example, we assume this when we say that comparison-based sorting ...
5k 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?
88k 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 ...
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 ...