# All Questions

45,999 questions
Filter by
Sorted by
Tagged with
3 views

### Doubt regarding conjugations of permutations

I was studying the Barrington Theorem in https://homes.cs.washington.edu/~anuprao/pubs/CSE531Sp2020/lecture2.pdf when I found a doubt regarding permutations. Particularly, with conjugations. It is ...
• 362
3 views

### Is the set of instances of PCP, which have a solution, semi-decidable?

My idea was that it is because we can construct a TM M' that simulates a TM M that is to find a solution for a PCP instance. M' accepts if M accepts, rejects if M rejects, and doesn't halt if M does ...
5 views

### Is this definition of the class P correct?

The definition of P is given by the union of all DTIME($n^k$) languages for $k >= 0$, where DTIME($n^k$) is the set of languages for which there exist a TM time-bounded by $T(n) = O(n^k)$. However, ...
15 views

### Best data structure in C++ to store bodies in an N-body simulation?

I am writing an N-body simulation in C++ that has to be able to deal with large N ($N \le 10^6$). Everything has been going well so far, but now that I have started to code in collisions between ...
6 views

### Where can I find a list of logics with their corresponding calculus and computation phenomena?

I was watching some lectures by Prof. Pfenning on Proof Theory. He gave a list for some different kinds of judgments along with their calculus and computation phenomena that they can represent or ...
• 101
8 views

### MIX computer's field specification

Section 1.3.1 describes Knuth's imaginary MIX computer. Its instructions consist of five (variable) bytes. I'm trying to understand the field specification byte. A field is of the form (L:R) where L ...
9 views

### Reduction from Diophantine Equation Problem to Halting Problem

I want to study the reduction from the Diophantine Equation Problem (Hilbert's tenth problem) to the Halting problem. Can you either explain it to me or give me a credible source from which I can ...
• 1
11 views

### Range updates in segment trees of sorted arrays (merge sort trees)

I understand range updates in segment trees using lazy propagation where each node is an integer. Merge Sort Tree (source GFG): https://media.geeksforgeeks.org/wp-content/uploads/20220722205737/...
9 views

### How to make LR(1) grammar for sequence that cannot have more "Down" than "Up" for any given prefix

I am working on a problem that asks me to write an LR(1) grammar that satisfies the following rules: Consider a robot arm that accepts two commands: "Up" puts an apple in the bag and "...
26 views

### How to find the standard theta notation of this?

Hi i am practising standard theta notation: How could i find the standard theta notation of the following : 2n + 3n^2(log n)^3 + 2 and ...
• 3
1 vote
11 views

### Applying Baum-Welch to multiple observed sequences iteratively

When using the Baum-Welch algorithm to train a hidden markov model you normally repeat it on some observed sequence iteratively until your values converge. If you have multiple observed sequences, ...
• 11
66 views

### Is this sorting problem NP-complete?

Consider array $A=(a_1,a_2,...,a_n)$ such that $a_i$s are positive integers. Moreover, we have $k$ binary tuples, each with length $n$. In each iteration, we choose one of those tuples, and decrease ...
13 views

### How is it possible to "lock" device's software?

How is it possible to "lock" device's software (i.e. only the manufacturer's own software works)? Can the CPU do that? It feels unnatural because hardware is "dumb" and not "...
14 views

### Binary Sequence

Computer is used to control security lights given as 0110010. The system is programmed in that there will be light when 10101010 trigger switch is activated while switching signal is given as 01010. ...
1 vote
18 views

15 views

37 views

### Finding the length of the longest palindrome in the given array

The problem that I'm trying to solve is: Given an array of length N, I want to find the length of the longest palindrome in the given array. With palindrome, we refer to a word, phrase, or sequence ...
19 views

92 views

### What is this question actually asking for me to solve?

(15 marks) Suppose a ray comes from a point (2, 8) and hits at mirror point (6, 6). Assume that perpendicular vector a point (6, 6) is 𝑛̅= (0, 3). Find the reflection emitting point from (6, 6). [...
38 views

### Goedel's theorem, halting problem and irreducible complexity

I have a vague idea on the tip of my mind that I can only convey through examples. Gödel's theorem states that some systems (ZFC, for example) are always incomplete in the sense that new axioms (which ...
15 views

### Difference between systems of systems, distributed systems, and complex systems?

Also, what are the learning resources about them. For example, an introductory book about their design and architecture
• 97
22 views

### Whether the class of languages with time complexity between polynomial and exponential is an NP language？

We know that the P language class is a polynomial-time solvable language class, and the NP language class can be determined in exponential time. And there exist some languages that can be decided only ...
• 183
1 vote