Wild Florida Gator living in Arabia
Mohammad Al-Turkistany, Ph.D. in Computer Engineering, University of Florida
Chairman of Computer Engineering Department, Umm Al-Qura University, Saudi Arabia
"The reasonable man adapts himself to the world; the unreasonable persists in trying to adapt the world to himself. Therefore all progress depends on the unreasonable".
George Bernard Shaw
|
1d
|
|
comment |
An NP-complete variant of factoring. @MarzioDeBiasi Thanks a lot. |
|
May
21 |
|
awarded | Popular Question |
|
May
20 |
|
awarded | Popular Question |
|
May
18 |
|
comment |
Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems? As for the evidence for one-way functions, see this post: cstheory.stackexchange.com/questions/8829/… |
|
May
18 |
|
comment |
Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems? Short answer, $P \ne NP$ assumption alone is not helpful. We need at least the existence of one-way functions. |
|
May
18 |
|
comment |
Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems? Yes. NP-complete problems are hard in the worst-case. It is possible that the majority of instances of an NP-complete problem are efficiently solvable. However, Russell Impagliazzo proposed a world (Pessiland) where average-case NP-complete problems exist but one-way functions do not exist. In this world, we can not generate hard instances of NP-complete problem with known solution. |
|
May
14 |
|
awarded | Caucus |
|
May
8 |
|
awarded | Popular Question |
|
May
8 |
|
comment |
Why economists should care about computational complexity @Salamon What flaws did you find ih his reasoning? |
|
May
8 |
|
comment |
Why economists should care about computational complexity Try this, Markets are efficient if and only if P=NP; arxiv.org/pdf/1002.2284.pdf |
|
May
5 |
|
revised |
Consequences of OWFs for Complexity added 9 characters in body |
|
May
5 |
|
revised |
Consequences of OWFs for Complexity added 61 characters in body |
|
May
5 |
|
answered | Consequences of OWFs for Complexity |
|
May
5 |
|
comment |
Consequences of OWFs for Complexity @SashoNikolov Thanks. You are right. |
|
May
5 |
|
comment |
Consequences of OWFs for Complexity In Descriptive Complexity, by Immerman Corollary 7.23 implies that P=NP iff P=PH. Have look at this post: cstheory.stackexchange.com/questions/5463/… |
|
May
5 |
|
comment |
Consequences of OWFs for Complexity Yes, existence of OWFs implies that the polynomial hierarchy is infinite since P=NP iff P=PH. |
|
May
2 |
|
answered | Diophantine equations and complexity classes |
|
Apr
28 |
|
comment |
Notions of information content and randomness of binary square matrix OK. Here is an example: Given $n \times n$ binary matrix, if you permute the rows and the columns you will get two equivalent matrices in terms of adjacency information while the two corresponding $n^2$ vectors would have different information content. |
|
Apr
27 |
|
comment |
Notions of information content and randomness of binary square matrix Aha. I am not necessarily interested in current notions but rather interested to measure the intutive concept of adjacency in $n^2$ string that is not captured by current notions. |
|
Apr
27 |
|
comment |
Notions of information content and randomness of binary square matrix I still argue that a $n^2$ binary string with H-adjacency and V-adjacency defined by some function holds more information than just plain $n^2$ binary string. I hope my motivation is clear now. |
