All Questions
46,364
questions
0
votes
0
answers
10
views
If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$
I have the problem
If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$
To solve this I am using a result $BP\cdot NP\subset NP/poly$ which I can prove (not doing here). I have two solutions but ...
- 101
1
vote
2
answers
15
views
Deterministic infinite automaton equals a normal DFA?
Assume we have a deterministic infinite automaton. $DIA = (Q, δ, q_0, F)$. Meaning there is no limit to the number of states. I want to prove or disprove that this module equals a normal DFA.
Attempt
...
- 13
1
vote
1
answer
18
views
Algorithm to find a set of nodes with a smaller set of neighbours in a bipartite graph
Given a bipartite graph, find a set of nodes on one side that has greater cardinality than the set of its neighbours on the other side.
This is a conceptually simple problem, but I suspect it is ...
- 267
0
votes
0
answers
20
views
Desgining NFA under certain constraints
I've got homework to design NFA to accept a set of strings over {a,b,c} in which each string of the language satisfies: "cac" is a substring and "cc" is not a substring and the ...
- 129
0
votes
0
answers
18
views
How fixed point Decimal to Binary conversion algorithm works?
I'm reading a book which says that to transform a number from decimal to binary with fixed point representation you have to follow these steps:
Take the integer part (the one before the point) of the ...
- 293
0
votes
0
answers
13
views
Ford-Fulkerson algorithm running in pseudo-polynomial time
Consider a graph with $n$ nodes and $m = \mathcal{O}(n²)$ edges. The maximum capacity among all edges is denoted by $C$. The running time is given by: $\mathcal{O}(nmC)$
If I consider the input size ...
- 1
0
votes
1
answer
40
views
What recurrence describes the time complexity of this algorithm?
The problem is as follows:
The input is an array $A$ of $n$ natural numbers such that:
(1) if the maximum occurs in $A[p]$ for an index $p$, then $$A[1] \leq \ldots \leq A[p-1] \leq A[p]$$ and $$A[p] ...
- 103
1
vote
0
answers
17
views
Is Dijkstra's algorithm used in cheapest airfare calculators?
Is Dijkstra's shortest-path graph algorithm used in cheapest airfare calculators like Expedia or CheapAir?
- 155
0
votes
1
answer
24
views
64-bit Xorshift with 2^96 or 2^128 period
Can we create Xorshift generator, as Marsaglia in "Xorshift RNGs" does, using 64-bit numbers, but with period 2^96 or 2^128?
He proposed PRNG with period 2^96:
...
- 133
1
vote
0
answers
7
views
Difference between Hadlock's algorithm and A* search
I recently read about pathfinding algorithms on grids. It seems two of the most popular are Lee's algorithm and Hadlock's algorithm. Other than the space optimizations that these algorithms employ, it ...
- 205
0
votes
0
answers
19
views
Finding the Optimal Palette for a Set of Images
Motivation
I want to draw pictures using indexed colors. As I have limited space for colors per-palette, I want to choose palettes in an intelligent fashion, based on the pictures I want to draw. The ...
- 1
0
votes
0
answers
14
views
What are the similarities and differences between dependent function application and ML functor application?
Advanced Topics in Types and Programming Languages gives this rule section 2.2 gives this rule for dependent function application:
$$\frac{\Gamma \vdash t_1 : (\Pi x : S.T) \quad \Gamma \vdash t_2 : ...
- 316
0
votes
3
answers
33
views
How do you stop an algorithm at a specific run time?
so I'm trying to write an algorithm in C to play the game of Reversi. I've already written in basic minimax algorithm yet I am not very satisfied with it. I want to implement alpha-beta pruning to my ...
- 101
2
votes
2
answers
28
views
Is there a common notation for describing this operation $coNP\; ? \; NP = DP$?
While working with complexity classes, I've come along the definition of $DP$ (or $D^p$):
$$DP = \{L_1 \cap L_2 \mid L_1 \in NP \text{ and } L_2 \in coNP\}$$
I am interested in a different (and much ...
- 301
1
vote
0
answers
17
views
Finding an approximate double-zero using binary search
Let $f$ be a continuous real function on $[-1,1]$. The function is accessible via queries: for any $x$, the value of $f(x)$ can be computed in constant time.
If $f(-1)<0$ and $f(1)>0$, then by ...
- 5,818
-1
votes
0
answers
11
views
What is encryption and how is it used in protecting files?
What is encryption? How does it work to protect files? Please explain. Oh and how can I do that by myself???
- 1
1
vote
0
answers
10
views
Simplified Memory Bounded A*
I have been studying the SMA* algorithm and I am having trouble understanding the backup operation. Specifically, I don't understand why the f value of a child node should be the maximum of its own f ...
- 11
0
votes
1
answer
28
views
Designing a DFA with nth character condition for any integer n
Let n be an integer. How can I write finite automata for the language L?
L = {W∈{$0,1,2$}*| The $n_{th}$ from last letter in w is $0$}.
(Please suggest answers; not hints.)
Attempt
Using Regex, I ...
- 13
0
votes
1
answer
14
views
Uses of Hex and Octal numbers in programming
Where are these number patterns, Octal and Hex, being used? I read this but I want to know where they are used in programming.
- 1
0
votes
1
answer
24
views
Workers with certain strength carrying boxes. (Greedy)
I just had an algorithms exam and had the following problem:
Supposed there are $n$ workers and $n$ objects. Each worker has a strength, $s_i$ and each object has a weight $w_i$. Each worker needs to ...
- 1
1
vote
1
answer
52
views
As far as we know, what does GPT-4's training data look like?
I was asking ChatGPT local history questions, because I knew many of the answers and could test the robot. But lots of details were wrong and while it can write citations, it won't disclose its ...
- 111
0
votes
1
answer
19
views
Prove that the problem MATCH is NP-complete
The problem MATCHED is defined as follows: given an infinite set S of strings of arbitrary length over the alphabet {0, 1}, determine if there exists a character of length n over the alphabet {0, 1} ...
0
votes
0
answers
31
views
How do you deal with Skolem functions which escape their scope in elimination rules?
If you have an elimination rule for tuples which introduce the left and right pair into the type checking context, what do you do if the type of one of the elements is quantified and has been ...
0
votes
0
answers
28
views
How to calculate the upper bound of the gredient of a multi layer ReLu neural network
Layers: We shall denote in the following the layer number by the upper script $\ell$. We have $\ell=0$ for the input layer, $\ell=1$ for the first hidden layer, and $\ell=L$ for the output layer. The ...
0
votes
3
answers
38
views
How do you write a logic function to determine if one 2s complement binary number is less than another?
Working on logic design in class, and I'm trying to figure out how to write a specific logic function [and by write, I mean something along the lines of (x NOR y) OR (a NOR b), for example]
It asks to ...
- 1
0
votes
1
answer
35
views
Is there a maximal set of programs that terminate?
It seems useful to characterize terminating programs. While trying to formulate that as a well-defined question I was wondering about the following problem:
Is there a maximal decidable set of ...
- 1
1
vote
2
answers
37
views
Explanation of Cook-Levin Suitable for First Years
TLDR; Looking for Explanation of Cook-Levin theorem palatable to CS first years who are theory averse
I'm a prof. teaching first year algorithms+programming and want to give my students a taste of ...
- 11
0
votes
1
answer
32
views
Parsing algorithms
I have experimented with a grammar that I could turn into a strict left-to-right finite state automaton driven algorithm (bottom up, table driven). The FSA could be complex, that's not a problem. It ...
- 111
1
vote
0
answers
17
views
Does adding a polynomial-time function impact APX-hardness?
I have two optimization problems $A$ and $B$, and I recently managed to show that there exist functions $f$ and $g$ that are computable in polynomial time, such that for any instance $x$ of $A$ there ...
- 11
-1
votes
0
answers
24
views
What is a practical example of a Context-Free Grammar?
I've been looking into Abstract Syntax Trees and came across the idea of a Context-Free Grammar which is described in the following way:
In formal language theory, a context-free grammar (CFG) is a ...
- 99
1
vote
0
answers
24
views
Did Jon von Neumann know about Claude Shannon's work when he wrote the "First Draft of a Report on the EDVAC?"
In the "First Draft" JvN described an adder circuit to do binary addition, which was a much faster way of doing computer addition than using decimal lookup tables as the ENIAC had done. JvN'...
- 111
0
votes
0
answers
22
views
Why $rank(C|_V)\geq rank(C)$ for $r$-rank preserving subspace for depth 3 circuits
I was reading Deterministic Black Box PIT Testing for Generalized Depth 3 Arithmetic Circuits - Karnin and Shpilka
In the Theorem 3.4 they told $rank(C|_V)\geq rank(C)$
We have $C|_V$ which is ...
- 101
-2
votes
1
answer
38
views
Find Number of subsequences such that bitwise OR is same as sum
Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0<=Ai<=Bi. Count How many ...
- 7
0
votes
0
answers
25
views
Upper bound of traveling salesman problem via dynamic programming
For a set of $n$ cities, the total time to compute OPT (see Fomin & Kratsch, Chapter 1) is given to be
\begin{equation}
\sum_{k=1}^{n-1} O\left(\left(\begin{...
- 101
0
votes
0
answers
30
views
Function types in Computer Science Metanotation
See Guy Steele's slides for what I refer to by "Computer Science Metanotation", specifically the bits about BNF.
I often make use of the BNF syntax observed there, as a substitute for ...
- 111
0
votes
0
answers
15
views
Is proof based calculus more useful to become an AI researcher and an advanced specialist?
I don't know which single variable calculus course to choose: mit 18.01 or mit 18.014( proof-based calculus). I want to become an advanced specialist
0
votes
1
answer
48
views
Knapsack with no capacity
Given a set $S$, a value function $v(s)$ and a cost function $c(s)$ for all $s \in S$, and integers $B$ and $K$, the classic formulation of the Knapsack problem asks if there is a subset $S' \subseteq ...
0
votes
0
answers
18
views
How to prove (L+M)* = M*.(L.M*)*
Question is to simplify (LM*)* and I couldn't figure out a way to simplify it. Since (L+M)* = M*.(L.M*)*, I guess we can say that it cannot be simplified more. So how do we prove that they are the ...
- 55
0
votes
0
answers
23
views
Is the existence of multiple algorithms for one problem the example of application of homotopy type theory?
There are problems which can be solved by multiple different algorithms, like shortest-path in graph: https://en.wikipedia.org/wiki/Shortest_path_problem. By Curry-Howard isomorphishm, each problem is ...
- 1,381
1
vote
0
answers
22
views
Efficient generalized suffix array/tree construction for prefix trees
Is there any algorithm that can efficiently construct a generalized suffix tree or array (or something similar) for a set of strings represented by a prefix tree (trie)?
In particular, I'm wondering:
...
- 1,217
0
votes
1
answer
67
views
Optimization of algorithm
Question:
There are N soldiers standing in a straight line with ID 1 to N: [1,2,3,4,5]
You are given array of IDs of length K in the order they are called : [3,1,2,1]
When a ID is called the soldiers ...
- 101
3
votes
2
answers
100
views
An algorithm that is $O(n^{\log(n)})$
After having searched for a while, and after having read this
https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities
I was just wondering: is ...
- 131
0
votes
0
answers
21
views
I'm having trouble storing the value in R0 into the correct memory location (LC-3 Assembly)
Here is my LC-3 Assembly code.
It is designed to add up the 10 values in x3100 through x3109 and store them in x310A.
It correctly adds the values, storing the total in R0, however I cannot seem to ...
- 1
0
votes
0
answers
14
views
Zero Knowledge Protocol for Search Problem
Does anyone know any zero-knowledge protocol that addresses the search problem, i.e. finding the output to a query without revealing the query or any other output?
-1
votes
2
answers
60
views
A new algorithm for determining if a number is prime or not
This approach has been on my mind for quite some time. I did come up with it myself, I searched some methods for determining prime numbers but never came across anything similar to this.
...
- 11
-2
votes
1
answer
87
views
Is DNA computation Turing complete?
I have heard DNA being referred to as "code", this is because it is an instruction set which dictates the bodies' properties. However, DNA (as far as I have learned), has no conditional ...
1
vote
0
answers
26
views
prove the correctness of greedy algorithm on interger optimize
Let $n$ and $r$ be positive integers. For i = 1,2,...,n, let $f_i$ be a univariate real-valued function defined in the integer domain and let $f_i(x_i)$ be $-\infty$ for negative integer $x_i$.
Any ...
- 173
0
votes
0
answers
7
views
Role of State Dynamics Target Network in DDPG
I am trying to create a variant of DDPG in MATLAB that has no action-value $\langle Q \rangle$ net, but that instead works with networks $\langle V \rangle, \langle f \rangle, \langle r \rangle$, and ...
0
votes
1
answer
23
views
Time complexity to convert a truth table to a boolean circuit
The SAT problem is often explained in terms of truth tables. Given some random boolean circuit, calculate its truth table; does there exist an output of $1$ in the truth table?
But how about going the ...
- 73
0
votes
1
answer
11
views
Confusion with Execution of NDFA
I do not understand the "execution graph" (I think that's what it's called) of the following Non-Deterministic Finite Automata, given on pg 48-49 of Sipser's Intro to TCS (3rd edition):
And ...
