Computer Science

« first day (2235 days earlier) ← previous day next day → last day (2193 days later) »

3:14 PM

Let P1 and P2 be two problems such that P1 is polynomial time reducible to P2, the time complexity of this reduction is O(n^2), and the time complexity of solving P2 is O(n^4). What can you say about the time complexity of the problem P1 ?

We typically reduce a known problem to an unknown problem...in this case, an unknown problem is being reduced to a known problem....what would be the time complexity in this case?

Computer Science Meta

3:43 PM

Q: Burninate tag: pseudocode

We have four questions tagged "pseudocode". This question seems to have no value: any question that requests an algorithm would be off-topic if it required a specific language, so tagging a "Please give me an algorithm to do X" question with "pseudocode" is redundant; the answer to any question...