nir shahar
• Member for 1 year, 7 months
• Last seen this week

What about $\Sigma^*$ and $\Sigma^*\setminus\{11\}$?

$0^*$ will generate any number of repetitions of $0$, and will also generate the empty string $\epsilon$. So, the problem with your expression is that $11$ is also accepted, since we can write it as $$... View answer 2 votes Lets define the following bipartite graph: The nodes in the first group, will be the elements from A, and the nodes in the second group will be the elements from B. Add an edge between every ... View answer 2 votes Your intuition is a great starting point. To formalize this, consider denoting by F(n) the number of times the col-- happens, or equivalently, the total time you waste in the while loops. Notice, ... View answer Accepted answer 2 votes The first argument does help with a rigorous refutation for the statement. If you want to really be formal, here is how you should approach it (its not a formal proof, but more of a sketch for how you ... View answer 2 votes Here is another hint: how would you find whether an element is valid in O(1) in this auxiliary stack? Try to somehow "connect" the index at the original huge array, to the place in the ... View answer Accepted answer 2 votes Lets start with transforming a\oplus b = True. This is simple enough, since it happens if and only if either one of a or b is True and the other is False. We can easily encode it as follows: ... View answer Accepted answer 2 votes For any language L, and for any oracle O, we have that L^O=L^\overline{O}. Substitute NP instead of O, and \Sigma^P_2 instead of L and you get that {\Sigma^P_2}^{coNP}={\Sigma^P_2}^{NP}... View answer Accepted answer 2 votes Let us keep this in mind: w\in A/B \iff \exists z\in B: wz\in A Since we are working with semi-decidable machines, then we have no problem iterating over all z's until we find a good one! ... View answer Accepted answer 2 votes Yes (assuming you meant that we can choose e freely. If it isn't the case, the answer is "no"). Let P_1:=a\rightarrow v_1\rightarrow v_2\rightarrow \dots \rightarrow b be the shortest ... View answer Accepted answer 2 votes Take a look at my answer here. Basically, the different areas of math are used in different areas of computer science as well. Specifically for algorithms, for example, knowing probability theory can ... View answer Accepted answer 2 votes This is indeed a correct approach. It can be improved further by using binary search on k, but you have to be careful with it since you want to multiply a small number of matrices (and computing A^... View answer Accepted answer 2 votes There is an O(n) solution, using a nice trick: Keep track of the different values you have already seen in an auxiliary hashmap, called seen. Now, loop over the elemnts of the array (the original ... View answer 2 votes An n\times n grid takes n^2 memory cells. You don't need to remember the "history" of the game, as it is irrelevant. View answer 2 votes It seems you are struggling to understand the definition of the halting problem. So I will try my best to define it so you can understand easily. Our task, is to create some algorithm, which we will ... View answer Accepted answer 2 votes For every position 0\le i\le 1000, enumerate over all strings that have e at their i'th spot. This can be easily done as you need to enumerate on strings with length i-1 and strings with ... View answer 2 votes For every edge (u,v) with weight 2, create a new node w_{u,v}. Discard the edge (u,v), and instead of it add two edges (u,w_{u,v}) and (w_{u,v},v) with weight 1. Now you can use a ... View answer Accepted answer 2 votes The statement is false. Take a look at the following graph: In one BFS run, you will get the following tree: That has a distance of 1 between u and v, while in a different run, you could get ... View answer Accepted answer 2 votes Let L\in NP. Thus, L\le_p A. Since A\in coNP, then L\in coNP. Hence, NP\subseteq coNP. Now, let L\in coNP. Thus, \overline{L} \in NP and therefore \overline{L}\le_p A. From reduction ... View answer Accepted answer 2 votes if a problem is in NPH then it is also in NPC This statement is incorrect. A language is in NPC if it is in NPH and it is in NP. Answer 4 is incorrect as well since that would imply that ... View answer Accepted answer 2 votes The core idea is good. You might want to elaborate more on how this process is done in detail: Let us keep in mind that an OWF is a function F that can be computed in poly(n) time but F^{-1} ... View answer Accepted answer 2 votes Lets say there are N(n) partitions. Then, for each partition you do O(n^c) work (important note: make sure for all partitions this is the same O(n^c). That is, for this particular c, for all ... View answer 2 votes Try to think in practical terms what would actually happen if your computer used a big quantum: Lets say our quantum is 1 second. Now, say you browse in a browser (for example, CS stack exchange), and ... View answer Accepted answer 2 votes From what I understand, the problem the paper is trying to solve is a gap problem of deciding whether X is (k,b)-clusterable, or at least \epsilon-far from being (k,2b)-clusterable. Since they ... View answer 2 votes In my opinion, programming is magic: you get into a small dark room and smash keyboards and poof you got infinite money. Just kidding! programming isn't magic at all, nor witchcraft. If you will learn ... View answer 2 votes The second approach is technically the correct interperation. When we say "a verifier gets a certificate c that looks like [...] and computes something", then we actually mean that this ... View answer 2 votes It is theta of 2^{2n}:$$2^{2n+2}=4\cdot 2^{2n}=\Theta(2^{2n})

It is defined by the function $d_s(x)=distance(s,x)$. Basically, its just the distance function where we fix the source node to be $s$.
An (infinite) string is uniquely identified by a function $s:\mathbb{N}\rightarrow \{A,B\}$, such that $s(n)$ is the $n$'th character in the string. The number of such functions is known to be: $|\{A,... View answer Accepted answer 2 votes You are right that$N$is used in this way. If you want a proof without$N$, you will have to prove in some other way (for example, by sentence induction) that$M'\models\psi\$. I understand you that ...