chazisop
Reputation
290
Next privilege 500 Rep.
Access review queues
 May14 awarded Caucus Jul2 revised Prime number generator, how to make changed question objective Jun30 answered Prime number generator, how to make Jun14 comment Reductions for regular languages? I would recommend crossposting this to cstheory stackexchange, even if an answer is already given, for future users' convenience. Be sure to mention that you crossposted it on both sites if you do. Mar16 awarded Yearling Jan5 answered Is Turing completeness monotone with respect to Cook reductions? Jan5 comment Expanding this boolean expression A more general comment: If you work with small boolean expressions (<4 variables) a truth-table for both expressions can always determine equivalence. Aug11 comment satisfiable assignment close to an unsatisfiable assignment For those not familiar with complexity, Levon's error is using "definitely" , since we do not know if P is equal to NP or not. Aug4 comment Applications of Convergence of a series in Algorithms Sometimes convergence is used to show that an algorithm is correct or behaves like it should, e.g. in machine learning and probabilistic algorithms. Aug4 comment Find the NFA for the language $\{ w | \text{ w contains an even number of 0s, or contains exactly two 1s } \}$ Raphael , you are right. The extra advice that small examples from exercise books will be ok, even if there is an exponential blowup (still , it can be time-consuming). As for the link, it was downloading a .pdf.gz file that wasn't working with my reader, so I changed it to a plain html view of the slides. Aug4 revised Find the NFA for the language $\{ w | \text{ w contains an even number of 0s, or contains exactly two 1s } \}$ added 69 characters in body Aug3 answered Find the NFA for the language $\{ w | \text{ w contains an even number of 0s, or contains exactly two 1s } \}$ Aug2 comment non time constructible functions I believe the Inverse Ackermann function is not-time constructible. Jul25 comment How to determine in polynomial time if a number is a product of two consecutive primes? Yes but this algorithm is for general use, while this question addresses a specific factoring problem. Special conditions can make the difference between NP-completeness and membership P, or even computability and uncomputability. Jul23 comment Can an algorithm be faster than O(1)? Let's assume that the particle model you describe is indeed less than constant in running time. My point is that under any model, you must observe the output somehow, therefore you need at least 1 step. As a small correction, the omega in my previous comment was supposed to be capital. Furthermore, we must consider not what model are possible, but rather what models better fit computation as it is in our universe. So is there a computational procedure that takes less than constant time and if yes, does it matter to us? Jul22 comment Can an algorithm be faster than O(1)? Given your examples, e.g. the gears model, a suitable measure of complexity is needed (e.g. number of revolutions). I believe the issue that all algorithms are $\omega(1)$ is simple as stating that all algorithms must output at least 1 bit of information. As a sidenote, big-oh notation was there half a century before modern digital computers. Apr19 comment What is a good language to develop in for simple, yet customizable math programs? I believe you should ask your question is more appropriate for stackoverflow.com Apr13 comment Any concise way to represent this in a formula? Just keep in mind that if you are too concise you risk confusing your audience. Apr12 awarded Citizen Patrol Apr10 comment What is undecidability @persononinternet I can guarantee you that you cannot simulate a 1x1x1 cm cube of the real world on the best supercomputer there is now. The reasons are due to physics but the borders between physics and computational models can be thin, so you can interpet them in a computation light. Simulations like the ones of the recent tsunami ignore many events as irrelevant and only monitor the progress of events that will have a significant effect.