« first day (1621 days earlier)      last day (2008 days later) » 

YOUSEFY
YOUSEFY
10:19 AM
@ThomasKlimpel Do we have theory that tells us that all parallel model of computation are polynomialy reducible to each other (just like in case of Turing machine and RAM, and other models in exact computation) because If I have such a theorem, then I can design an algorithm for one model regardless of other models. I just read a few pages of Blelloch and Bruce. I think I will find an answer in the book of Greenlaw, Hoover, and Ruzzo!
in this page: http://blog.computationalcomplexity.org/2002/09/complexity-class-of-week-factoring.html
Fortnow states "The class UP∩co-UP is arguably the smallest interesting complexity class not known to have efficient algorithms and, assuming factoring is hard, really does not have efficient algorithms." As I understand is that "decision problem of factoring" is in P (by AKS Primality test algorithm) while "function problem of factoring" is in NP∩co-NP, besides other problems. I do not understand what does he mean by UP intersects co-UP is the smallest class that doesn't have an efficien…
Note that in this class "UP∩co-UP" we have only decision problems according to wikipedia https://en.wikipedia.org/wiki/UP_(complexity)
So, it doesn't contain a function problem. So, this is why i said function problem is in NP intersects co-NP
 
 
6 hours later…
vzn
vzn
4:18 PM
@YOUSEFY sounds a lot like NC=?P problem to me.
NC (complexity)
In complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem is in NC if there exist constants c and k such that it can be solved in time O(logc n) using O(nk) parallel processors. Stephen Cook coined the name "Nick's class" after Nick Pippenger, who had done extensive research on circuits with polylogarithmic depth and polynomial size. Just as the class P can be thought of as the tractable problems (Cobham's thesis), so NC can be thought of as the...
 

« first day (1621 days earlier)      last day (2008 days later) »