Recent Questions - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-12-12T22:46:26Z https://cs.stackexchange.com/feeds https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/118427 1 Why does $L = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belong to $\mathcal{P}$? NimaKimi https://cs.stackexchange.com/users/101486 2019-12-12T21:05:02Z 2019-12-12T21:26:36Z <p>My professor said that the <em>non-regular</em> language <span class="math-container">$L_{1} = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$</span> belongs to <span class="math-container">$\mathcal{P}$</span>. I do understand that all regular languages belong to <span class="math-container">$\mathcal{P}$</span> as it's easy to determine and so can be computed in <span class="math-container">$\mathcal{O}(n^k)$</span>, but why do most <em>non-regular</em> languages not belong to <span class="math-container">$\mathcal{P}$</span> but <span class="math-container">$L_{1}$</span> does? Is it also possible to give an example of a language <span class="math-container">$L$</span> that does not belong to P?</p> https://cs.stackexchange.com/q/118426 0 Using Lean Theorem Prover from command line [closed] user3565552 https://cs.stackexchange.com/users/113216 2019-12-12T20:39:56Z 2019-12-12T20:39:56Z <p>I have read this link about using Lean: <a href="https://leanprover.github.io/reference/using_lean.html" rel="nofollow noreferrer">https://leanprover.github.io/reference/using_lean.html</a> and am able to use Lean with VSCode, but I still have questions about using Lean from the command line.<br> 1. When I download the lean binaries, there is a lean and leanchecker binary. What does each one do, and is there any documentation on using them?<br> 2. What is LEAN_PATH? I wrote a Lean file that uses the Lean library list type. I want this to to be checked from the command-line, that is when I write a #check command in the file, on VSCode the #check is underlined in blue letting me know that it checks; I want to do the equivalent from the command-line. But when I run the Lean binary on my file, it says 'error: file 'data/list' not found in the LEAN_PATH'. Now, I have the entire Lean repository (<a href="https://github.com/leanprover/lean" rel="nofollow noreferrer">https://github.com/leanprover/lean</a>) in my system and it also contains the built binaries - this is what it took to get Lean to work on VSCode (that and telling VSCode where the head of the repository is). Also, the head of this repository is in my PATH but what does it mean for data/list to be in my LEAN_PATH? </p> <p>I'm not able to find documentation for these specifics, most of them talk about using Lean from VSCode or Emacs. If I missed it, please point me to the right resource. Thanks!</p> https://cs.stackexchange.com/q/118424 0 Under the assumption that $P \neq NP$, prove or disprove the following propositions Gianni Spear https://cs.stackexchange.com/users/53941 2019-12-12T20:21:53Z 2019-12-12T20:21:53Z <p>I have problem to point 7 and 8.</p> <p>Let <span class="math-container">$L1,L2 ∈ \{0,1\}^*$</span>. Under the assumption that <span class="math-container">$P \neq NP$</span>, prove or disprove the following propositions:</p> <ol> <li><span class="math-container">$L_{1} ∈ P ⇒ L_1^c ∈ NP$</span>.</li> </ol> <p><em>[<strong>FALSE</strong>] because with <span class="math-container">$P \neq NP$</span>, the complementary class of P is co-P, and not NP</em></p> <ol start="2"> <li><span class="math-container">$L_1 &lt;_P L_2 ⇔ L_1^c &lt;_P L_2^c.$</span></li> </ol> <p><em>[<strong>TRUE</strong>] by the polynomial time reducible definition</em></p> <ol start="3"> <li><span class="math-container">$L_1 &lt;_P L_{SAT} ⇒ L_1 ∈ NPC.$</span></li> </ol> <p><em>[<strong>FALSE</strong>] by NP-complete definition (i.e., every <span class="math-container">$L_1$</span> in NP is polynomial time reducible to <span class="math-container">$L_{SAT})$</span>.</em></p> <ol start="4"> <li><span class="math-container">$L_1 &lt;_P L_{SAT} ⇒ L_1 ∈ NP.$</span></li> </ol> <p><em>[<strong>TRUE</strong>] by NP-complete definition (i.e., every <span class="math-container">$L_1$</span> in NP is polynomial time reducible to <span class="math-container">$L_{SAT})$</span>.</em></p> <ol start="5"> <li><span class="math-container">$L_1 &lt;_P L_2 \ and \ L_2 &lt;_P L_1 ⇒ L_1,L_2 ∈ P.$</span></li> </ol> <p><em>[<strong>FALSE</strong>] by NP-complete definition (i.e., <span class="math-container">$L_1$</span> and <span class="math-container">$L_2$</span> are NPC).</em></p> <ol start="6"> <li>A reduction function f is a one-to-one correspondence.</li> </ol> <p><em>[<strong>TRUE</strong>] by the polynomial time reducible definition</em></p> <ol start="7"> <li>If we restricted the input set of CLIQUE to graphs G = (V, E) of degree at most 7, then the resulting subproblem would be in P.</li> </ol> <p><em>[<strong>?</strong>]</em></p> <ol start="8"> <li>If there is an algorithm for CLIQUE with running time <span class="math-container">$N^{O(log N)}$</span>, then every other problem in NP has an algorithm with a running time of the same form.</li> </ol> <p><em>[<strong>?</strong>] From the theory, I know that when problem A is efficiently reducible to problem B, an <strong>efficient solution</strong> to B can be used to solve A efficiently. But <span class="math-container">$N^{O(log N)}$</span> it is not an efficient solution.</em></p> https://cs.stackexchange.com/q/118423 0 Convert a polygon mesh into a b-spline surface Mohbenay https://cs.stackexchange.com/users/51341 2019-12-12T20:08:48Z 2019-12-12T20:08:48Z <p><span class="math-container">$\textbf{Problem:}$</span></p> <p>Getting a <span class="math-container">$\textit{polygon-mesh}$</span> as input, I have to construct a surface that looks exactly to the given input. My task is to generate a <span class="math-container">$\textit{b-spline}$</span> surface that exactly looks like the connected polygon mesh. It is obvious that my <span class="math-container">$\textit{b-spline}$</span> surface has to have a degree of one in both directions <span class="math-container">$\textit{u}$</span> and <span class="math-container">$\textit{v}$</span>.</p> <p><span class="math-container">$\textbf{Output:}$</span></p> <p>As an output for my solution. I have to generate a matrix of <span class="math-container">$\textit{control point}$</span> that represent that generated surface.</p> <p>One property of this matrix is that each elements of each row and column are connected with each others. If our control points matrix is a <span class="math-container">$n \times m$</span> matrix, then let <span class="math-container">$C_i$</span> a column of this matrix with <span class="math-container">$C_i = &lt;e_{1i}, e_{2i}, \dots, e_{mi}&gt;$</span> then there must exist path in the polygon from <span class="math-container">$e_{1i}$</span> to <span class="math-container">$e_{mi}$</span>.</p> <p>One thing to consider if there is no edge between <span class="math-container">$e_{ji}$</span> to <span class="math-container">$e_{(j+1)i}$</span>, we can construct one as long as this edge lies inside the polygon.</p> <p><span class="math-container">$\textbf{my trivial idea}$</span></p> <p>Assuming that the polygon has <span class="math-container">$n$</span> nodes. I create <span class="math-container">$n$</span> other nodes inside the polygon near each original node. I create then a <span class="math-container">$2 \times n$</span> matrix. The first row contains all the points constructing the polygon. Second row contains the corresponding additional inserted node. In order to connect two additional inserted nodes, i have to make sure that the line between two nodes is kept inside the polygon.</p> <p>This idea works only for simple structure and the complexer is the polygon the hard to find these additional points.</p> <p>Any good solutions maybe ?.</p> https://cs.stackexchange.com/q/118421 0 ln(n) + 1 Approximation for Set Cover constructions Tarang Saluja https://cs.stackexchange.com/users/113047 2019-12-12T19:18:27Z 2019-12-12T19:18:27Z <p>Set Cover Problem: Given a set <span class="math-container">$X$</span> and a collection of subsets <span class="math-container">$S_1, S_2, \ldots S_m \subseteq S$</span>, we want to find the smallest cardinality of a set of <span class="math-container">$k$</span> elements <span class="math-container">$\{i_1, \ldots i_k \}$</span> such that <span class="math-container">$\displaystyle \bigcup_{i = 1}^k S_{i_j} = X$</span>. </p> <p>Let <span class="math-container">$o$</span> be the size of optimal solution for the Set Cover problem. We know that there exists an approximation algorithm which yields solution <span class="math-container">$k$</span> such that <span class="math-container">$\frac{k}{o} \leq \ln(n) + 1$</span>. As such, the approximation ratio is unbounded and can achieve large values for large <span class="math-container">$n$</span>. Note that this algorithm is greedy and repeatedly chooses the set which covers the largest amount of elements that haven't been covered yet. </p> <p>What is a methodical way to construct a set of size <span class="math-container">$n$</span> and all of the input subsets, such that increasing the size of <span class="math-container">$n$</span> monotonically increases the approximation ratio? </p> https://cs.stackexchange.com/q/118420 0 Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$ Doesbaddel https://cs.stackexchange.com/users/95950 2019-12-12T18:57:38Z 2019-12-12T20:27:12Z <blockquote> <p>I want to find a Context-Free Grammar for <span class="math-container">$L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$</span></p> </blockquote> <p>I've tried the following:</p> <p><span class="math-container">$G=(V,\Sigma,R,S)$</span> with <span class="math-container">$\Sigma=\{a,b,c,\lambda\}$</span>, <span class="math-container">$V=\{S,B\}$</span>, <span class="math-container">$S=S$</span> and <span class="math-container">$$R=\{S\to \lambda\mid aSc\mid B,\;B\to bBc\mid \lambda\},$$</span> which would output <span class="math-container">$L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$</span>, in my opinion. I've tried to test my grammar by applying the rules in different combinations and I didn't spot any error yet.</p> <p><em>So I'm asking myself:</em><br> Is there a way to to see if <span class="math-container">$L(G)=L$</span> or do I need to assume, that I've done everything correctly after testing some cases?</p> https://cs.stackexchange.com/q/118415 0 Can polynomial many-to-one reduction be done to a specific problem instance? carpenter https://cs.stackexchange.com/users/111792 2019-12-12T16:30:58Z 2019-12-12T17:05:08Z <p>Let's say I reduce the problem <span class="math-container">$A \in L$</span> to <span class="math-container">$B \in K$</span> , with a function <span class="math-container">$f: \Sigma^{*} \rightarrow \Gamma^{*}$</span> such that <span class="math-container">$w \in L \Leftrightarrow f(w) \in K$</span> . I know if I want to solve <span class="math-container">$A$</span>, given some polynomial time algorithm for <span class="math-container">$B$</span>, I just have to transform <span class="math-container">$A$</span> to <span class="math-container">$B$</span> and solve <span class="math-container">$B$</span>. So it can be thought as: </p> <blockquote> <p>The reduction must be done from arbitrary instance of <span class="math-container">$A$</span> to a legal instance of <span class="math-container">$B$</span></p> </blockquote> <p>My question is, do I have to reduce to <em>arbitrary</em> instance of <span class="math-container">$B$</span> or <em>some</em> instance of <span class="math-container">$B$</span>? I.e. reduction from TQBNF to Generalized Geography is done to some valid graph instance, but there exist many more valid instances of Generalized Geography.</p> https://cs.stackexchange.com/q/118414 0 How to convert a centralized algorithm to a distributed algorithm? Rupok Saha https://cs.stackexchange.com/users/113212 2019-12-12T16:12:25Z 2019-12-12T17:31:26Z <p>Is there any algorithm or procedure to convert a centralized algorithm to a distributed algorithm? Is there any theoretical result or relevant complexity analysis? </p> https://cs.stackexchange.com/q/118411 -2 data hazard about five-stage instruction pipeline Tom https://cs.stackexchange.com/users/113211 2019-12-12T15:56:32Z 2019-12-12T15:56:32Z <pre><code>or <span class="math-container">$2,$</span>5,$3 sw <span class="math-container">$1,3($</span>2) lw <span class="math-container">$5,1($</span>6) </code></pre> <p>Does data hazard occur in these three instructions? My answer is no but I am not sure.</p> <p>Also, is <code>3($2)</code> the same memory address as <code>$5</code> ?</p> <blockquote> <p>Blockquote</p> </blockquote> https://cs.stackexchange.com/q/118410 0 Splitting filename text by underscores using RStudio [closed] user80046 https://cs.stackexchange.com/users/113210 2019-12-12T15:40:01Z 2019-12-12T15:40:01Z <p>In R I'd like to split file names in the format "a_b_c_d.jpg I need the a and b value If I use strsplit I get "a" "b" "c" "d.jpg" but i want  a  b and for c, d it's unimportant what's happening with it.</p> <p>And in the end i want to use the  and  but i don't know how to call up the value in it.</p> <p>Thanks for helping me with doing my astrological research about the sun activity :) </p> https://cs.stackexchange.com/q/118409 2 Weighted Average of Multi-Output Neural Networks user121169 https://cs.stackexchange.com/users/113207 2019-12-12T13:24:20Z 2019-12-12T17:47:48Z <p> discusses how to construct an ensemble of neural networks by giving each network a certain weight <span class="math-container">$\alpha_i$</span>: <span class="math-container">\begin{equation} f_\mathrm{GEM}(\boldsymbol{x}) = \sum_{i=1}^N \alpha_i f_i(\boldsymbol{x}) \end{equation}</span> where each <span class="math-container">$\alpha_i$</span> is obtained using a correlation matrix which is defined in the following way: <span class="math-container">\begin{equation} C_{ij} = E[m_i(\boldsymbol{x}) m_j(\boldsymbol{x})] \end{equation}</span> where <span class="math-container">$m_i(\boldsymbol{x}) \equiv f(\boldsymbol{x}) - f_i(\boldsymbol{x})$</span>, with <span class="math-container">$f(\boldsymbol{x})$</span> being the target function and <span class="math-container">$f_i(\boldsymbol{x})$</span> being the output.</p> <p>I was wondering how should one compute <span class="math-container">$C_{ij}$</span> when the neural network has multiple outputs. Would one firstly calculate <span class="math-container">$\boldsymbol{m}_i(\boldsymbol{x}) \equiv \boldsymbol{f}(\boldsymbol{x}) - \boldsymbol{f}_i(\boldsymbol{x})$</span> for all examples and then compute <span class="math-container">$C_{ij} = E[\boldsymbol{m}^T_i(\boldsymbol{x}) \boldsymbol{m}_j(\boldsymbol{x})]$</span>? I tried doing that (with MNIST data) but the accuracy was not better than when taking a simple average of all the networks in the ensemble. I would appreciate any help on this.</p> <p> M. P. Perrone and L. N. Cooper, "When networks disagree: Ensemble methods for hybrid neural networks," in Artificial Neural Networks for Speech and Vision. Chapman and Hall, 1993, pp. 126-142.</p> https://cs.stackexchange.com/q/118408 0 Doubt in effective memory access time in case of n level paging + TLB Nascimento de Cos https://cs.stackexchange.com/users/105282 2019-12-12T13:16:04Z 2019-12-12T13:16:04Z <p>I am getting confused with calculation of EEMAT(Effective memory access time). I decided to close the book and think on my own and make an equation. Please see whther this is correct or not. I thought a lot and also refereed google but i am lost. Please help!</p> <p>Let TLB hit ratio = x.</p> <p>TLB access time = c</p> <p>main memory access time = m</p> <p>page fault rate = p; page fault service time = S</p> <p>First i will access TLB. In case of TLB hit i will directly access main memory(so time here = c+m in case of TLB hit)</p> <p>If TLB Miss, then i will have to access via page table. I am assuming here n level page table(so n page tables needed to access main memory).</p> <p>In case of TLB Miss, i will access page table(n level) --> it can be hit or miss. If page hit, then time = c+(n+1)m</p> <p>If page fault, time = c+m+(n+1)m --> <strong>TLB access time + first i access page table to know that there is no valid frame in 1st level page table itself</strong>(i got another doubt here, in case of page fault in n level paging, valid bit is 0(invalid page) in 1st level or any of n levels or in nth level page table???) <strong>+ n level page table access in main memory + finally main memory</strong></p> <p><strong>So EEMAT = x(c+m)+(1-x){ (1-p)[(n+1)m] + p[S + m + (n+1)m ] }</strong></p> <p>Is this correct???</p> <ul> <li><strong>My another doubt:</strong></li> </ul> <p>in case of page fault in n level paging, valid bit is 0(invalid page) in 1st level or any of n levels or in nth level page table???</p> https://cs.stackexchange.com/q/118405 0 Equivalence between two different definitions of PAC learnable Binyamin Riahi https://cs.stackexchange.com/users/113204 2019-12-12T11:18:05Z 2019-12-12T11:18:05Z <p>In a course on machine learning, I saw a definition of "PAC learnable class". But on a paper of C.Laskowski, there is a slightly different definition and I cant prove the equivalence between them. I joined pictures of the two definitions.</p> <p>Thanks <img src="https://i.stack.imgur.com/viFfx.jpg" alt="![">]<a href="https://i.stack.imgur.com/viFfx.jpg" rel="nofollow noreferrer">1</a></p> https://cs.stackexchange.com/q/118403 -1 Question about pipeline cycle hazard [closed] Goku https://cs.stackexchange.com/users/113197 2019-12-12T08:11:53Z 2019-12-12T08:11:53Z <p><a href="https://i.stack.imgur.com/LzMHe.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/LzMHe.png" alt="some data from program simulation is given here"></a></p> <p>The question is to find the hazards within Cycle 1 to 6 and their correct values, as well as the type of the harzards</p> <p><a href="https://i.stack.imgur.com/XaZOI.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/XaZOI.png" alt="The answer should be given in this form"></a></p> <p>Thank you!</p> https://cs.stackexchange.com/q/118402 0 decidability and reducibility Diana https://cs.stackexchange.com/users/113198 2019-12-12T08:07:18Z 2019-12-12T08:07:18Z <p>I am a bit confused on how I can show the finiteness problem is undecidable using Rice’s Theorem.</p> <p>So I’ve got something like B = { | M is a TM and L(M)- finite}. I thought I could reduce A TM (determine whether a TM accepts a given input which I already know is undecidable) to B but then I’m not sure how I would construct/ describe a new Turing Machine that decides my A?</p> https://cs.stackexchange.com/q/118401 -1 Program v. Algorithm v. function Matthew Walkup https://cs.stackexchange.com/users/113195 2019-12-12T08:02:18Z 2019-12-12T19:48:05Z <p>I'm a beginner with C++ and have been going thru SICP. Recently, I have started to grapple with the difference of a program v. algorithm v. function and want to know, would this be a good comparison be:</p> <p><strong>What a program is to an algorithm and an algorithm is to a function, is what an anatomical system is to a tissue and a tissue is to a cell?</strong></p> <p>I'm sure it can be said better, but I've imbibed a bit tonight.</p> <p>A system executes a 'self contained' process like digestion, but it requires MORE than just its whole. That's where it's tissue comes in. The tissue not only interface internally, but externally to the system. Ex, The smaller intestines account for nearly all the body's water absorption. However, the tissues relies on 'the cell' which is different depending on the type of tissue, even muscle tissue is difference. Ex, the intestinal peristalsis (or, the wave like motion of the intestines to push food through) is far different from the musculoskeletal contractions largely due to the difference of myocyte (muscle cell).</p> <p>Sorry if this makes no sense. Feel free to tell me I'm wrong: "I thrive off of criticism" - Ryan Howard</p> https://cs.stackexchange.com/q/118399 0 Probability of detecting errors in codewords NoNeural https://cs.stackexchange.com/users/113192 2019-12-12T04:38:45Z 2019-12-12T16:02:31Z <p>I have been struggling with the below question for quite some time, and I don't have a pointer to move forward.</p> <blockquote> <p>A certain Error Control Coding scheme using block codes takes an input block (dataword) of 500 bits and appends a 50 bit code to produce a 550 bit codeword which is then transmitted across channel that causes individual bits to flip with a probability of 0.1 independently. The pairwise Hamming distances between all the codeword pairs is so large that the probability of an error occurring that converts one to the other can be neglected, except as follows: two codewords C 1 and C 2 have a Hamming distance of 10, and two codewords C 3 and C 4 have a Hamming distance of 6. Assuming no knowledge about what datawords may be more or less likely to be desired to transmit, what is the probability that a given block transmission will be corrupted by the channel but the error will go undetected by the receiver? You may answer with an expression, but the answer has to be completely numerical (no symbols).</p> </blockquote> <p>My thought process about this question is that the probability needs to be calculated as such : Pr(Selecting either C1 or C2) * P(error in C1 or C2) + Pr(Selecting either C3 or C4) * P(error in C3 or C4).<br> I feel the Pr(error) is given by a binomial distribution of 55CX(0.1)^x(0.9)^550-x where X=10 or 6. </p> <p>First, am I thinking about the problem correctly ? If yes , how do i derive the probability of selection of a particular codeword ? </p> <p>Edit: I don't have the exact source per se, because this question is from a random uni final exam that I found on the internet. I am prepping for my own exam, and came across this question.</p> https://cs.stackexchange.com/q/118398 0 What is the logical reasoning behind Arden's Theorem proof of unique solution? langtutheky https://cs.stackexchange.com/users/113190 2019-12-12T03:55:58Z 2019-12-12T20:24:13Z <p>Here is the <a href="https://www.geeksforgeeks.org/ardens-theorem-in-theory-of-computation/" rel="nofollow noreferrer">proof</a> for Arden's Theorem assertion that R=QP* is the <strong>unique (only solution)</strong> to R=Q+RP. My question is: what is the logical reasoning to prove that any equation is the <strong>unique (only solution)</strong>? Particularly in this case, how can the procedure </p> <blockquote> <p>(1) recursively substitute R in R=Q+RP with Q+RP, then (2) establish the recursive definition of R, and finally (3) generalize the definition to R=QP*</p> </blockquote> <p>logically lead to the proof that R=QP* must be the <strong>unique (only solution)</strong>?</p> <p>Here is an example of the proof:</p> <p>Given that P and Q are two regular expressions over <span class="math-container">$\sum$</span>, and P does not contain <span class="math-container">$\epsilon$</span>.<br> <a href="https://i.stack.imgur.com/CsYMN.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/CsYMN.png" alt="Arden&#39;s Theorem Unique Solution Proof"></a></p> https://cs.stackexchange.com/q/118392 0 triangle inequality TSP is NP-complete? Patrick https://cs.stackexchange.com/users/111595 2019-12-11T23:53:48Z 2019-12-12T16:05:27Z <p>I have been reading online source and it mentioned triangle inequality TSP is NP-complete but without proof. In general, the reduction from HAM-cycle problem to TSP works for asymmetric and symmetric TSP problem. So, I wonder how to start a basic approach to prove triangle inequality TSP is NP-complete. </p> https://cs.stackexchange.com/q/118388 1 Dijkstra without decrease key user3726947 https://cs.stackexchange.com/users/113182 2019-12-11T22:58:42Z 2019-12-12T11:45:32Z <p>I was reading though this <a href="https://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf" rel="nofollow noreferrer">paper</a>, which suggests using dijkstra without edge relaxation, but to rather to just insert new nodes, cf page 16 for the pseudo code. But to me the code looks wrong. I think the comparison should be </p> <pre><code>k &lt;= d[u] </code></pre> <p>and also the update of the d[u] in the next line seems redundant to me. I think the delete-min operation can never return a vertex with distance label k which is strictly less than d[u] since whenever a vertex distance pair is inserted into the priority queue the distance array d is updated. Am I correct in assuming that this is a mistake in the paper?</p> https://cs.stackexchange.com/q/118383 0 Validity of self refering state with linear temporal logic 'X' connective Papaya Automata https://cs.stackexchange.com/users/92841 2019-12-11T18:33:08Z 2019-12-12T12:58:02Z <p><a href="https://i.stack.imgur.com/QGqSm.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/QGqSm.png" alt="enter image description here"></a></p> <p>Lets say we have model like the one above or a similar one where a node refers back to itself. </p> <p>Now let's say if I want to know the validity of the formula:</p> <p><span class="math-container">$M, s_2 \models Xr$</span> </p> <p>Will this be valid or not. In my textbook it says :</p> <p><span class="math-container">$\pi \models X\phi$</span> iff <span class="math-container">$\pi^2 \models \phi$</span></p> <p>If we are starting at state 2 then our path would be <span class="math-container">$S_2 -&gt; S_2 -&gt; ...$</span></p> <p>So, I'm not sure since state 2 is not actually transitioning to another states like State 0 or 1. Otherwise would transitioning to the same state in a path <span class="math-container">$\pi$</span> be enough to satisfy the "X" connective.</p> https://cs.stackexchange.com/q/118360 1 Proof of Fundamental Lower Bound on Regret Niels Uitterdijk https://cs.stackexchange.com/users/113152 2019-12-11T11:08:07Z 2019-12-12T10:54:53Z <p>Online Convex Optimization sees optimization as a continuous process in which the algorithm learns new aspects of the problem and improves upon. </p> <p>Every iteration consists of the player making a decision <span class="math-container">$x_t$</span> from a convex and bounded decision set <span class="math-container">$\mathcal{X}$</span>. After we made our decision the adversary returns the loss for our decision, <span class="math-container">$f_t(x_t)$</span>. Often the gradient of the loss function is accessible too, <span class="math-container">$\nabla_{x_t}f_t(x_t)$</span>. This loss function <span class="math-container">$f_t$</span> can change, follow any distribution, but is always convex and bounded. </p> <p>Any OCO algorithm (such as online mirrored descent or regularized follow the leader) aims to minimize regret, the loss of your decisions minus the loss of the best decisions in hindsight. This is defined as <span class="math-container">$\mathcal{R}_T := \sum_{t=1}^Tf_t(x_t) - \min_x \sum_{t=1}^Tf_t(x)$</span>. </p> <p>Using (a.o.) two bounds; <span class="math-container">$$||x - y|| \leq D \quad \forall \quad x, y \in \mathcal{X}$$</span> <span class="math-container">$$||\nabla_x f_i|| \leq G \quad \forall \quad i \leq T \quad \forall \quad x \in \mathcal{X}$$</span> it is possible to derive an upper bound on regret for most algorithms. Online Gradient Descent is for example guaranteed to converge with <span class="math-container">$\mathcal{R}_T \leq \mathcal{O}(GD\sqrt{T})$</span>. Now, different algorithms benefit different convergence rates. Although most algorithms converge <span class="math-container">$\Big(\lim_{T\rightarrow\infty}\mathcal{R}_T/T = 0\Big)$</span>, no matter how good your algorithm, at iteration 0 you have no information about <span class="math-container">$f_t$</span>. It takes a certain number of iterations before you can make optimal decisions. Therefore there must be a fundamental lower bound any algorithm can achieve as an upper bound. It turns out to be <span class="math-container">$\mathcal{O}(GD\sqrt{T})$</span>. </p> <hr> <p><strong>Theorem 3.2, in  states:</strong> <em>Any algorithm for online convex optimization incurs <span class="math-container">$\Omega(DG\sqrt{T})$</span> regret in the worst case. This is true even if the cost functions are generated from a fixed stationary distribution</em></p> <p>They don't proof it however. They give an example which sketches the proof, but if someone could explain the proof or give a different proof that any algorithm will have a an upper bound on its regret greater or equal than <span class="math-container">$\mathcal{O}(GD\sqrt{T})$</span>. </p> <hr> <p>** E. Hazan - Introduction to Online Convex Optimization ** <a href="https://arxiv.org/pdf/1909.05207.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1909.05207.pdf</a></p> https://cs.stackexchange.com/q/118353 0 A question about Pipeline Cycle ChristiePPP https://cs.stackexchange.com/users/113149 2019-12-11T06:25:57Z 2019-12-12T07:54:35Z <p>This is my question, I am so confused with my answer, looking for help! <a href="https://i.stack.imgur.com/hZBMj.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/hZBMj.png" alt="enter image description here"></a></p> <p>This is my answer: <a href="https://i.stack.imgur.com/FSpko.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/FSpko.png" alt="enter image description here"></a> Explanation: At the third instruction, instruction is waiting before ID, thus, no stalling is needed. (it does not have any changes before decoding. At the forth instruction, which is the store word, the$2 is available at the 10th cycle until it is written back before instruction decoded. At the last two instruction, there is no data hazard, so the instructions run without any hinder.</p> <p>However, the instructor said that if an instruction is waiting before ID, the next instruction of IF phase should be start at 6th instead of 3rd (what I did)</p> <p>Therefore, I am looking for help and want someone to discuss and check the idea with me. Thanks a lot for help!</p> <p>For instance, which of the two IF is appropriate?</p> https://cs.stackexchange.com/q/117972 9 How to devise an algorithm to generate a random but valid train track layout? David James https://cs.stackexchange.com/users/31249 2019-12-02T22:07:56Z 2019-12-12T21:33:10Z <p>I am wondering if I have quantity C of curved tracks and quantity S of straight tracks, how I could devise an algorithm, (computer assisted or not), to design a "random" layout using all of those tracks, such that the following rules are satisfied:</p> <p>1) The tracks, when all connected, form a closed (continuous) loop for the train to go around.</p> <p>2) Ramps, bending of tracks, bumping of tracks, crossing of tracks are all not allowed.</p> <p>3) C and S will both be even numbers. An example would be C=20 and S=10. Note that it takes 12 curves in the same orientation to make a complete circle of 360 degrees so at least 12 of those curves need to be oriented the same way to complete the 360 degrees. The others can "zigzag" as long as the net result is 360 degrees so the train has a complete loop.</p> <p>Straight tracks are about 10 inches (25.4 cm) long and curved tracks are about 12.4 inches (31.6 cm) long (down the center, following the curve) and curve 30 degrees. The "ties" on the tracks have a maximum width of 3 5/8 inches (9.2 cm). I placed a straight and curved track on top of each other and measured that the 12.4" (31.6 cm) curve has 12" (30.5 cm) of linear length (in the same direction as the straight), and 3" (7.6 cm) of bend (in the perpendicular direction of the straight). A 12C circle has diameter of 47.5" (120.6 cm) from center to center of the tracks on opposite sides.</p> <p>All measurements are approximate.</p> <p><strong>UPDATE</strong></p> <p>I re-measured the tracks using many more of them to help eliminate errors and somewhat to my surprise, the length of the straights are NOT 10 inches, they appear to be about 9.78 inches. This has a significant impact on the matching of zigzag curves to straights. Originally I thought 4 zigzag curves = 5 straights but that is not quite correct. 4 curves has about 47" of linear distance so 5 straights at 9.78" each would be 48.9", almost 2 inches longer. So the trick it to find the LCM (Least Common Multiple) of 47 and 9.78. It turns out to be 235. 235 = 47*5 and 235/9.78 = 24.028... (close enough). That means 20 zigzag curves is virtually the same as 24 straights in linear length. Luckily I have 26 straights so I just barely made it. The 2 leftover can easily be positioned elsewhere in the layout.</p> <p>Another thing I discovered is that if I zigzag the curves 2 the same orientation at a time (OOCCCCOO), then 8 of those has a linear distance of only 83 inches, not 94 inches like if I alternate curves (OCCOOCCO). The LCM of 83 and 9.78 is about 166. So 16 of those curves has the same linear length as 17 straights. That is useful to know because I have 44 curves and only 26 straights but if I do this substitution, I can help make up for that.</p> <p>If I zigzag the curves 3 at a time (OOOCCCCCCOOO) and bend it just slightly, I can get the exact linear length of 10 straights (about 97.8 inches).</p> <p><strong>END OF UPDATE</strong></p> <p>So would the computer program have to create a geometric model and remember the exact positions of each track or is there some simpler way to code this? I want to be able to "push a button" and the computer "spits out" a valid "new" layout for me.</p> <p>I want to give this working algorithm to kids that use the trains, so they don't get frustrated attempting a layout that doesn't work and then they try to bend the tracks to make it work or have to leave out a few track pieces cuz they don't fit. A computer can create a valid layout using all of the tracks and if the algorithm is good, perhaps in a few seconds. This is to help prevent frustration for them.</p> <p>I have some coding skills but I need to know an algorithm first before I can code something meaningful (other than just testing a few parts of a candidate algorithm)</p> <p>What I am thinking is I could have the computer model the tracks using a smaller (scaled down) representation. I think it could then just "place" the tracks in the candidate layout and check for collisions with other tracks already there.</p> <p>I am thinking there are probably better ways to do it though, so that is why I am asking here for some help/ideas. I really want to get this to work and I have the tracks here so I can use them to help verify if the algorithm is working.</p> <p>We can use C=20 and S=10 as the parameters to try to solve this because it is a reasonably small number of tracks (30 total). I am assuming if the algorithm is robust enough, C and S values can be changed at will and it will still work. For example, eventually I want to try C=44 and S=26.</p> <p><strong>Final word</strong></p> <p>Thank you all for your comments and suggestions regarding this question. I learned a lot too. As a kid I never really thought much about train tracks and how they fit together but as an adult, I can see it is a fascinating geometric problem and a very difficult mathematical counting problem to generate / figure out how many different (unique) track layouts there are. I hope you enjoyed this exercise as much as I did. The kids appreciate it too.</p> <p><strong>End Final word</strong></p> https://cs.stackexchange.com/q/108761 2 What's the flaw in the P != NP proof in the article "The Computational Complexity of the Traveling Salesman Problem" Yamar69 https://cs.stackexchange.com/users/102696 2019-04-30T14:44:12Z 2019-12-12T16:01:28Z <p>I am reading through some proof of inequality of <strong><em>P</em></strong> and <strong><em>NP</em></strong> but they are not accompanied by the flaws in the reasoning so I'm trying to find them by myself, just to see if I'm getting the logic right. As an example I am currently reading <a href="https://arxiv.org/pdf/cs/0611082.pdf" rel="nofollow noreferrer">this (very short) proof</a> that <strong><em>P != NP</em></strong> and for me the lack in the argomentation is the following: what the author writes about the algorithm is sacrosanct but does not deny in any way the possible existence of algorithms or tricks that would allow to solve the problem in polynomial time.</p> <p>Am I right on this one?</p> https://cs.stackexchange.com/q/105666 1 Proving correctness of the Newton's Method for finding the square root of a number Alex https://cs.stackexchange.com/users/101698 2019-03-16T16:14:09Z 2019-12-12T19:01:30Z <p>I'm trying to prove the correctness of this simple square root calculation algorithm using SPARK:</p> <pre><code>Y := X / 2.0; while abs (X - Y ** 2) &gt; Tol * X loop Y := 0.5 * (Y + X / Y); end loop; return Y; </code></pre> <p>The preconditions are that both X and Tol are greater then zero and the postcondition is simply the opposite of the while loop's condition.</p> <p>Are there any invariants of the loop above that may help? Or maybe a different algorithm (eg. bisection) would be a better choice? So far I've tried showing that the value of the square root is always between <code>Y</code> and <code>X / Y</code> but that didn't get me anywhere.</p> https://cs.stackexchange.com/q/105509 3 Building maze to maximize shortest path, may be given waypoints and teleports user1902689 https://cs.stackexchange.com/users/101550 2019-03-12T22:52:26Z 2019-12-12T12:01:30Z <p>How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (Assuming sizes between 8x8 and 30x30. Using C or C++ if that matters) Or, is this so complex that it would take way longer?</p> <p>There is an area, where an automated traveler follows a shortest path algorithm at all times. Playing the builder, find the way to maximize the number of points the traveler must visit.</p> <p>The area is typically between 8x8 and 30x30, given in the form:</p> <pre><code>.F...... ......a. ........ ........ .....1X. ........ .A...... ........ ..O..... .X...... ..X..... ..X..... </code></pre> <p>Where there is:</p> <ul> <li>Always a single <code>O</code>, the starting point</li> <li>Always a single <code>F</code>, the ending point</li> <li>Always many <code>.</code>, empty points that can either be traveled or built on</li> <li>Sometimes <code>X</code>, points designating they are blocked for traveling or building</li> <li>Sometimes pairs of letters (i.e. <code>A</code> and <code>a</code>, but never <code>F</code>, <code>O</code>, or <code>X</code>), indicating a teleport when visiting the uppercase letter for the first time to the lowercase letter</li> <li>Sometimes numbers (i.e. <code>1</code>), designating waypoints</li> </ul> <p>The automated traveler follows a shortest path algorithm at all times. It must begin at the starting point, if there are waypoints pass over them in order, and finish at the ending point. The traveler may pass over the ending point or subsequent waypoints early, but the game doesn't end and the waypoints aren't counted as visited, until they are the active next destination. If there are any, the traveler must not pay attention to any teleport spots; they must take the shortest path between points as if they cannot see these teleport spots. The exception to this rule is if there are multiple paths with the shortest length between last source to next destination and one of them travels through an active teleport spot, the path with the teleport must be taken. (Otherwise, can choose any of the multiple shortest paths.) If the shortest path forces them into a teleport spot, they teleport the first time they visit the uppercase letter to the corresponding lowercase letter. The traveler can move horizontally and vertically. The traveler can move diagonally between two points if the 2x2 square containing both points is clear of blocking points.</p> <p>So, if the traveler needs to travel from the lower left to upper right point, here they can move diagonally and only count 2 moves:</p> <pre><code>.. .. </code></pre> <p>But here, again traveling from the lower left to upper right point, they cannot move diagonally and must count 3 moves:</p> <pre><code>X. .. </code></pre> <p>The game always starts with an open path to reach all required destinations.</p> <p>You, the builder, get to take all of your actions first, and none once you decide you are complete and allow the traveler to begin. The builder can place additional <code>X</code> points that block travel on them, but they cannot make it impossible to reach any of the required destinations. The builder cannot place any other points, such as more teleports or waypoints. The builder cannot remove anything given to them already in the area (other than replace empty points.) Strategy may include blocking points to force: otherwise out of the way travel; backtracking; and traveling between teleports. Optimal strategy might include trying to connect the starting, ending, and destination teleport spots in short paths, and forcing a long backtracking path to waypoints.</p> <p>This is to come up with possible strategies for a tower defense game. Certain aspects of the game, such as multiple waves, limitations on resources, and attack towers, are ignored to simplify and just focus on the maze-like aspect of the game.</p> https://cs.stackexchange.com/q/104373 1 Multivariate polynomials Joe Smith https://cs.stackexchange.com/users/100466 2019-02-14T19:36:21Z 2019-12-12T10:03:10Z <p>Given a Diophantine equation <span class="math-container">$p(x_1,x_2,...,x_n)$</span>,</p> <p>Can I find a reduction from <span class="math-container">$\text{dioph}(\mathbb{N}) \leq \text{dioph}(\mathbb{N}_e)$</span>?</p> <p><span class="math-container">$\mathbb{N}_e$</span> is the set of even numbers.</p> <p>So I have to find a manipulation of <span class="math-container">$p$</span> such that I only have even numbers as solution.</p> <p>How can I do this? Unfortunately I have no Idea.</p> https://cs.stackexchange.com/q/98731 0 For which c, d is Gap2SAT[c, d] in P (such that 0<c<d<1)? student https://cs.stackexchange.com/users/92147 2018-10-17T17:31:23Z 2019-12-12T11:00:45Z <p>For which <span class="math-container">$c, d$</span> is <span class="math-container">$Gap2SAT[c, d]$</span> in <span class="math-container">$P$</span> (such that <span class="math-container">$0&lt;c&lt;d&lt;1$</span>)? </p> <p>(I know if d=1 then for each c it will be in P, however with which c,d such that <span class="math-container">$0&lt;c&lt;d&lt;1$</span> can I simply return YES?)</p> https://cs.stackexchange.com/q/57394 5 Predicting next action to take to reach a final state oalbrecht https://cs.stackexchange.com/users/51140 2016-05-13T02:52:23Z 2019-12-12T15:01:15Z <p>Does anyone know of an algorithm that could be used to determine the next action to take to reach a desired state when trained on time-series data? </p> <p>For example, a robot starts at a certain state, then takes an action to get to another state. This occurs continuously for many iterations (imagine the robot is randomly exploring a room). If the robot is at a specific starting state, and I desire the robot to end up in a different state, is there an algorithm that could recommend the best next action (or set of next actions) to take to reach that final desired state?</p> <p>One approach I've tried is to use a neural network with the current state and the next state being the input and the action to get from the current state to the next state being the output. The network would know for a single state how to get to a next desired state that is one action away. The issue is, what if the desired state is many actions away?</p>