Timeline for NC = P consequences?
Current License: CC BY-SA 3.0
33 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 3, 2018 at 17:15 | comment | added | Michael Wehar | @Turbo Question (3) might suggest for a good StackExchange question. I don't know what is the commonly accepted version of the $NC$ complexity class. | |
| May 3, 2018 at 17:10 | comment | added | Michael Wehar | @Turbo I find this back and forth to be rather exhausting. Why don't we just setup a time to chat over the phone or Skype instead. That way we can resolve any concerns that you might have. Thanks again and I hope that you have a great day!! :) | |
| May 3, 2018 at 17:09 | comment | added | Michael Wehar | @Turbo The reason that the proof I suggested works is because the paper establishes that $U_B$-uniform $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$ and for that matter all of the other notions of uniform $NC$ from the paper satisfy this as well. However, $P$-uniform $NC$ might not satisfy this because it's not known if $P \subseteq ATISP((\log(n))^{O(1)}, O(\log(n)))$ meaning that we can't simulate the part where we compute the circuits. | |
| May 3, 2018 at 17:06 | comment | added | Michael Wehar | @Turbo Thanks for all of your follow-ups!! I highly recommend that you read the paper that I linked because in it, it says that most of these notions of uniform $NC$ are equivalent. The paper however does not consider $P$-uniform $NC$ which could possibly be different as I have no way of proving that it is the same. | |
| May 2, 2018 at 6:39 | comment | added | Turbo | 5. What is the $NC^1$ versus $TC^0$ problem. Is it open for $U_B$, $U_{BC}$ and $P$ uniform NC? | |
| May 2, 2018 at 6:30 | comment | added | Turbo | 4. What is the largest known $X$ such that $X$-uniform $NC$ is proper subset of $PSPACE$? | |
| May 2, 2018 at 6:29 | comment | added | Turbo | 3. When wiki or we regular talk about $NC$ do they or we talk about $P$, $U_B$ or $U_{BC}$ uniform? | |
| May 2, 2018 at 6:29 | comment | added | Turbo | 2. Where is $U_{BC}$ uniform? Is it also not known to be proper subset of $PSPACE$ like $P$-uniform? Is $U_B$-uniform in $U_{BC}$-uniform in $P$_uniform? | |
| May 2, 2018 at 6:26 | comment | added | Turbo | @MichaelWehar 1. Why is your proof $U_B$ uniform is proper subset of $PSPACE$ and what would your proof need to improve this to $U_{BC}$ uniform and $P$-uniform are proper subset of $PSPACE$? | |
| May 2, 2018 at 3:18 | comment | added | Michael Wehar | @Turbo This definition describes the notion of $U_B$-uniform circuits. We have $U_B$-uniform $NC \subseteq ATISP((\log(n))^{O(1)}, O(\log(n)))$, but we don't know if $P$-uniform $NC \subseteq ATISP((\log(n))^{O(1)}, O(\log(n)))$. As a result, we have $U_B$-uniform $NC$ is a strict subset of $PSPACE$, but it is still not known if $P$-uniform $NC$ is a strict subset of $PSPACE$. Does that make sense? Please let me know if you have any further questions. Hope that you have a nice evening!! :) | |
| May 2, 2018 at 2:07 | comment | added | Michael Wehar | @Turbo Thank you for the follow-up!! I really think you should read the definition at the bottom of page 370 from: sciencedirect.com/science/article/pii/0022000081900386 | |
| May 2, 2018 at 1:42 | comment | added | Turbo | @MichaelWehar Sorry what is the difference between uniform $NC$ and $P$-uniform $NC$ and why is $PSPACE\neq NC$ absent in en.wikipedia.org/wiki/NC_(complexity)? So we know $NC\subsetneq PSPACE\subseteq EXP$? | |
| May 1, 2018 at 15:49 | comment | added | Michael Wehar | @Turbo As a result of my argument above, we have that their uniform $NC \subsetneq PSPACE$. However, $P$-uniform $NC$ is different from their uniform $NC$. As a result, it could still be the case that $P$-uniform $NC = PSPACE$. | |
| May 1, 2018 at 15:48 | comment | added | Michael Wehar | @Turbo Their first notion of uniform requires that the space used for constructing the circuits be bounded. For their notion of uniform $NC^k$, the space would be bounded by $log^k(n)$. Using this notion of uniform, they prove that uniform $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$. | |
| May 1, 2018 at 15:44 | comment | added | Michael Wehar | @Turbo I took a closer look at this paper: sciencedirect.com/science/article/pii/0022000081900386 | |
| Apr 30, 2018 at 16:46 | comment | added | Michael Wehar | @Turbo Thank you very much for the kind reply!! It may depend on the kind of uniform. For example, $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$ might only hold for Logspace-uniform NC. Let me think about it and get back to you. :) | |
| Apr 29, 2018 at 23:49 | comment | added | Turbo | @MichaelWehar I do not know but I have never seen anywhere that $NC\neq PSPACE$. In fact a comment in cstheory.stackexchange.com/questions/39046/… says $P-uniform NC^1=PSPACE$ is possible. I have posted a clarification query in cstheory.stackexchange.com/questions/40689/…. Do you think you can take a look? | |
| Apr 29, 2018 at 22:08 | comment | added | Michael Wehar | @Turbo Thank you for the comment!! Correct me if I'm wrong, but it seems that we have $$NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$$ and by applying a variation of the time hierarchy theorem along with the relationship between alternating time and deterministic space we have, $$ATIME(n) \subsetneq PSPACE.$$ By combining these two statements, we get $$NC = ATISP((\log(n))^{O(1)}, O(\log(n))) \subseteq ATIME(n) \subsetneq PSPACE.$$ | |
| Apr 29, 2018 at 14:15 | comment | added | Turbo | @MichaelWehar Do we know $NC^k\subsetneq PSPACE$ at any fixed $k$? In particular do we know $NC^2\subsetneq PSPACE$ and therefore $NC\neq PSPACE$? | |
| Nov 23, 2014 at 6:28 | history | edited | Michael Wehar | CC BY-SA 3.0 |
added 3 characters in body
|
| Nov 23, 2014 at 6:24 | comment | added | Michael Wehar | I intended to provide some more detail on what happens if NC=P. I've been thinking a bit about time-space trade-offs for alternating Turing machines so that influenced my perspective and was why I wrote the after thought. The comments were intended to give supplemental detail on the padding and help remedy any mistake. Thank you again, I appreciate the reply. | |
| Nov 23, 2014 at 5:52 | history | edited | Michael Wehar | CC BY-SA 3.0 |
deleted 236 characters in body
|
| Nov 23, 2014 at 1:01 | comment | added | Kaveh | I didn't finish reading your comments, I started but then I felt it is unnecessarily complicated and stopped reading. It can be fixed probably, but it seems like a long detour. As I wrote, the "after thought", which most of your post is devoted to proving if I understand correctly, is kind of obvious if you notice that the right-hand side is just NC^i: it is like PH=PSpace implying PH collapses. (I kind of fail to see how your answer helps in understanding what Ryan and Robin wrote.) | |
| Nov 22, 2014 at 22:10 | comment | added | Michael Wehar | Hi Kaveh, did I clear up the 'mistake'? It appears to work fine to me, but you expressed some doubt and your opinion is valued. | |
| Nov 22, 2014 at 22:04 | history | edited | Michael Wehar | CC BY-SA 3.0 |
added 58 characters in body
|
| Nov 19, 2014 at 17:28 | comment | added | Kaveh | Let me simplify the argument: CV is complete for P w.r.t. AC^0 reductions. If P=NC then NC collapses to some NC^i since they are closed under AC^0 reductions. | |
| Nov 19, 2014 at 6:56 | comment | added | Michael Wehar | So let's use random access to compute $n$ in binary using a form of binary search. This should take $\log^2(n)$ time. Now, $A'$ runs similar to $A$, but anytime that $A$ would use random access, $A'$ first compares the look-up address to $n$ (which was written in binary) to decide whether the character at that address is in $x$, the padding, or a blank symbol. This should blow-up the runtime by a $c\log(n)$ factor. Generalizing this construction appears to make (2) still work out (at least with just an extra log factor and larger constants). I'll review it again soon to make sure. | |
| Nov 19, 2014 at 6:55 | comment | added | Michael Wehar | Some alternating machine $A$ can solve $LinU$ in $\log^c(n)$ time. Rather than computing a many one reduction like I described, let's just build a machine $A'$ that simulates $A$ on input $(M',x')$. Since $M'$ is fixed, it can be hard coded into $A'$ with no problems. The input for $A'$ will be $x$, but we need quick access to $x'$ which is $x$ with a length $n$ padding of say 0's. | |
| Nov 19, 2014 at 6:47 | comment | added | Michael Wehar | Now, I'll propose a way to clear it up, but honestly, your input is appreciated because there is still more for me to learn on models of alternating machines with random access tapes. | |
| Nov 19, 2014 at 6:42 | comment | added | Michael Wehar | Hi Kaveh, thank you for the response. First let me describe the issue, then I'll try to clear it up. Now, say we are given a $2n$ time bounded TM $M$. Let's reduce $L(M)$ to $LinU$. Let $x$ be given. We can't just check if $(M,x)$ is in $LinU$. We have to modify $M$ slightly to obtain $M'$ and pad $x$ with $n$ characters to obtain $x'$ which has $2n$ characters in total. Then, we check if $(M',x')$ is in $LinU$. For the reduction, we map $x$ to $(M',x')$. We should be able to do this in linear time, but wait we need it to be done in $\log^c(n)$ time. | |
| Nov 19, 2014 at 5:05 | comment | added | Kaveh | The mistake is in the step that you move from LinU to LinTime: you ignore the overhead caused by reductions to LinU from LinTime machines. Just because a universal machine for the class C is in class C' doesn't mean C is a subset of C'. | |
| Nov 19, 2014 at 1:48 | history | edited | Michael Wehar | CC BY-SA 3.0 |
added 202 characters in body
|
| Nov 19, 2014 at 1:35 | history | answered | Michael Wehar | CC BY-SA 3.0 |