Theory

crypto noob
Hi, I'm a noob in cryptography. I wanna ask you if you can provide me a one-way-function which encrypts only about 4 bits, so that i can understand the systematics of creating one-way-functions and why they are so hard to reverse. Best Regards TK ... 18 Jul 2008 19:36

police
For years police have done crimes. If a lot of people look at my video the truth might be exposed. http://www.youtube.com/watch?v=BV_RaVVGrt8 Kurt ... 18 Jul 2008 17:32

Integer factorization reduction to SAT
Hello, Does anyone know if there is in existence an already-programmed executable (for Windows, preferably) that reduces an instance of the integer factorization problem to an instance of SAT? I posted on here a while ago asking how to perform such a reduction, and someone was kind enough to answer, but I do ... 18 Jul 2008 20:37

moving pairs
> > I saw something interesting about a grid pair puzzle problem that might be interesting. it's the problem where in a grid any size you say so many that are pairs. |1a|2a|3a| |2b|1a|3b| |4a|4b|5a| |6a|5b|6b| to make one move is to make the other of the pair move at th... 17 Jul 2008 23:01

reducing the factorization decision problem to SAT?
Hi, It's obviously possible to reduce an NP decision problem to SAT using Cook-Levin's mapping, but how does one do it in an "intelligible," simple way in practice for integer factorization? I know it's been done before, I just don't know how. Specifically, how do you reduce this decision problem... Given ... 16 Jul 2008 20:16

Resurrecting out-of-print math books
We have all experienced the frustration of discovering that a favorite book of ours has gone out of print. Bringing such a book back into print is no easy matter. Publishers want some assurance that the book will sell well enough for them to recoup the costs of republishing. Even in today's world of on-deman... 20 Aug 2008 22:08

Does the size of the stack of a PDA matter?
Hi, Consider a linear bounded pushdown automata (LBPDA) for which the size of the stack is bounded by some constant multiple of the length of the input. Is LBPDA's expressive power weaker than that of a normal PDA (i.e. a LBPDA cannot express some languages that can be done by a PDA)? Or, do both of these tw... 13 Jul 2008 20:15

TAUTOLOGY and SAT
Hi, I'm relocating this from the other thread I posted this in...I didn't intend to change the focus from the original poster's question, I apologize. But here is my question...is it true that TAUTOLOGY and SAT are polynomial time equivalent? It seems to me that they must be, because given a propositional for... 13 Jul 2008 15:07

Is this language context free?
Hi, This is a problem I have been working on for a while: Consider the following language L over the alphabet {a, b, c}. L = {xyz | x = y^R, z is a string with only c's, and lx|�� lzl }. Here y^R denotes the string obtained by reversing y. Is L context free? Thanks! Dillon ... 14 Jul 2008 02:23

NP problem and co-NP problem
Hello, please let me post my last question again because the old name seems to make problems with other threads. Why is it true that NP = co-NP if there is an NP-complete language L whose complement is in NP, too? My textbook argues as follows (cL denotes the complement of L): Because every NP language S is... 14 Jul 2008 10:35