Problem Detail: So, it’s known that PCP is undecidable even when we fix the number of tiles to $n geq 7$. I’m wondering, can anything similar be said for when there is a fixed word length? To be precise, here’s the Read More …
Category: Uncategorized
[Solved]: Log-Space Reduction $CO-2Col le_L USTCON$
Problem Detail: I want to show that $CO-2Col le_L USTCON$ (Log-Space reduction) $USTCON$ The $s-t$ connectivity problem for undirected graphs is called $USTCON$. [Input]: An undirected graph $G=(V,E)$, $s,t in V$. [Output]: 1 iff $s$ is connected to $t$ in $G$. Read More …
[Solved]: Analysing Space Complexity
Problem Detail: I have to compute the space complexity of this function: double foo(int n){ int i; double sum; if(n==0) return 1.0; else for(i=0;i<n;i++) sum+= foo(i); return sum } What I have done: When function is called, the activation record is Read More …
[Solved]: How can I translate this quantified logical expression into english
Problem Detail: I was reading chapter-1 The Foundations: Logic and Proofs from this book. The chapter gives example of translating English sentence : “There is a woman who has taken a flight on every airline in the world.” as follows: Introducing Read More …
[Solved]: construct a dfa that accepts odd consecutive number of 0’s and 1’s
Problem Detail: this dfa should accept only consecutive odd number of both 0’s and 1’s. example: 10001,1110001,10,01,011101. How can I draw its diagram? Asked By : user49697 Answered By : Rick Decker Here are a couple of hints to get you started. Could Read More …
[Solved]: Longest Common Subsequence Via Dynamic Programming
Problem Detail: I read the wikipedia page on the Longest Common Subsequence problem to understand the LCS Table approach, but it seems to result in different solutions given different orders of the original sequences. For example, the traceback table generated here Read More …
[Solved]: Why absence of surjection with the power set is not enough to prove the existence of an undecidable language?
Problem Detail: From this statement As there is no surjection from $mathbb{N}$ onto $mathcal{P}(mathbb{N})$, thus there must exist an undecidable language. I would like to understand why similar reasoning does not work with a finite set $B$ which also has no Read More …
[Solved]: Is my theorem about $P neq NP$ correct?
Problem Detail: It is known that there are problems in P that, provably, are not solvable in less than $O(N^k)$, for some $k$. Now consider some infinite set $K subseteq mathbb{R}^+_0$ such as K is unbounded from above (you can think Read More …
[Solved]: Is MIN or MAX-True-2-XOR-SAT NP-hard?
Problem Detail: Is there a proof or reference that $left{text{MAX},text{MIN}right}text{-True-2-XOR-SAT}$ is $NP$-hard, or that it (the decision version) is in $P$? Let: $$Phileft(mathbf xright)={hugewedge}_{i}^{n}C_i, forall_{C_i} left.C_i=(p oplus q)right|_{left(pin mathbf x veeneg pinmathbf xright),left(qin mathbf x veeneg qinmathbf xright)} $$ The $text{2-XOR-SAT}$ Read More …
[Solved]: Meyniel’s theorem + finding a Hamiltonian path for a specific graph family
Problem Detail: Let’s say we have a directed graph $G = (V, E)$ for which $(v, w) in E$ and/or $(w,v) in E$ holds true for all $v, w in V$. My feeling is that this graph most definitely is Hamiltonian, Read More …
