Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Code code:"if (foo != bar)"
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Bookmarks inbookmarks:mine
inbookmarks:1234
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with
Search options user 1546

Reference-request is used when the author needs to know about work related to the question.

2
votes
This seems to be related to the subgraph isomorphism problem which is in general NP-complete, even without any weights. The corresponding Wikipedia article claims that it can be solved efficiently in …
answered Sep 29 '10 by Raphael
1
vote
What machine model do you want to use? On RM, both are equally hard if you assume that $+$ and $<=$ are equally expensive (common assumption). On 1-TM, sum is slightly more expensive since we have …
answered Dec 3 '10 by Raphael
7
votes
We have been starting some reference questions on cs.SE covering typical (so far introductory) TCS problems. Besides general relevance, some answers contain methods that may not be known to every rese …
answered Jul 26 '12 by Raphael
5
votes
0answers
Given a set of pairs of words $P = \{(\alpha_1, \beta_1), \dots, (\alpha_n, \beta_n)\} \subseteq \Sigma^*\times\Sigma^*$, the Post Correspondence Problem (PCP) is to decide wether or not there are ind …
asked Jul 18 '11 by Raphael
5
votes
Instead of laboriously finding, justifying and analysing a specific model, you might want to use what real life data you have (if you have any). That means defining a generic probabilistic model and t …
answered Apr 29 '11 by Raphael
1
vote
I do not know when it came up, but the recursive solution for Towers of Hanoi is frequently used as introductory example. The problem originated before formal approaches on computation.
answered Nov 1 '10 by Raphael
18
votes
Deciding if a value exists in an array takes time $\Omega(n)$ (or $\Omega(\log n)$ if the array is sorted). Verifying that an array contains the given value at a given position is possible in time …
answered Nov 1 '15 by Raphael
1
vote
I will answer for the general setting. Assume a directed graph $G=(V, E)$ with costs as assumed in the question, that is the costs for entering a node depend on which edge it is left on and vice versa …
answered Feb 15 '11 by Raphael
9
votes
Many interesting problems that nature sciences come up with turn out to be NP-hard in the classical sense. While this notion is theoretically perfectly valid it does not help the biologist or physicis …
answered Nov 4 '10 by Raphael
0
votes
It was the first to have impact and thus has been established, especially in complexity theory. This is a weak reason, but people work that way. We work on old open problems first instead of declaring …
answered Dec 8 '10 by Raphael