Questions tagged [algorithms]
Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.
1,564
questions
3
votes
2
answers
398
views
A natural problem on "cartesian union" of set families (hypergraphs). Are there NP-complete problems related to the notion of cartesian product?
I'm curious whether the problem below is NP-complete.
I provide two simple definitions and one example at first.
Definition 1.
Let $\langle \cal S_i\rangle\substack{i\in I}$ and $\langle \cal S_j \...
- 41
3
votes
1
answer
554
views
How to partition a graph into N groups with M elements nearest?
This problem probably already here but I could not find the right words to find it.
I have a list with 1700 points (geographic coordinates) and a need to separate into 17 groups with 100 nearest. I ...
- 131
3
votes
1
answer
1k
views
#P version of SUBSET SUM
The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...
3
votes
1
answer
798
views
An algorithm for constructing the AR-quiver of a path algebra corresponding to a change in the orientation.
Considering the path algebra of the quiver $\mathbb{A}_n$, it is well known its Auslander-Reiten quiver with the canonical orientation of $\mathbb{A}_n$, that is, with all the arrows from, say, left ...
3
votes
1
answer
488
views
Efficient Algorithm for Matrix Version of Waring's Problem
Given an $n \times n$ matrix $A$ with entries in a commutative and associative ring with $1$ (say $Z[x_{1},\dots,x_{n^{2}}]$), the following paper guarantees existence of seven $B_{i}$s such that $A = ...
- 13.7k
3
votes
2
answers
617
views
Covering a sphere using reflections of an intersection of three lunes
I have been trying to figure this problem out for a while, and while I believe someone must have figured it out hundreds of years ago, I still can't quite get it.
Suppose we have a 3-dimensional ...
- 131
3
votes
1
answer
687
views
Quick algorithm for finding real solutions for a system polynomial equations
Would you please recommend a computer program that could give quick answer Yes/No for the question: does there exist a real solution of a given system of polynomial equations with integer coefficients....
- 1,271
3
votes
1
answer
1k
views
How I determine the probability that an unknown probability value is greater than others in a set?
I have a number of known beta distributions for different unknown probability values.
Given the beta distributions, I want to determine the probability that each specific unknown probability values ...
- 269
3
votes
1
answer
491
views
Compute number vertex disjoint cycles in graph surrounding a face
Hi all,
If anyone has insight into the following variant of the classic problem of packing vertex-disjoint cycle into graphs I would be interested.
Given a finite undirected graph $G$ embedded in $...
- 211
3
votes
1
answer
505
views
Approximating an integral representation of the Number Partition Problem
One can write out an integral whose solution gives the number of solutions to the NP-Complete Number Partition Problem and I'm wondering if anyone has an suggestions or ideas on who to solve or ...
- 513
3
votes
1
answer
234
views
Effect on connectivity when partitioning a graph
I have a connected graph $G=(V,E)$, $V$ being the vertex set and $E$ being the edge set. I partition the graph into components $C=\{C_1,\dots,C_n\}$ such that all $C_i$ are pairwise disjoint.
Take ...
- 591
3
votes
0
answers
36
views
Implementation of Friedman's algorithm of reconstructing simple polytopes
In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
3
votes
0
answers
87
views
Efficient multiplication of Cayley-Dickson numbers
The question was already asked here, but doesn't have any meaningful answer, hence I'd like to re-post it.
Assuming that we have an algebra with conjugation, we can use Cayley-Dickson construction to ...
- 1,141
3
votes
0
answers
64
views
Does this information theoretical thought experiment have a name or corresponding area of research?
I came up with the following thought experiment in my research in order to better understand the way Turing machines can transfer information through their tapes (the motivation is detailed below, isn'...
- 479
3
votes
1
answer
311
views
How to find the maximum of a sum of squares of sums?
Is there any better than a brute force method for finding the maximum
$$\max\limits_{ (d_{1},\dots,d_{n}) \in \mathbb Z_{m}^{n}} \sum_{j=0}^{m-1} \left(\sum_{i=1}^{n}v_{i,(j+d_{i})\bmod m}\right)^{2}$$...
user494931
3
votes
0
answers
336
views
Is this FFT algorithm known?
Recently I've been thinking about alternatives to the usual Cooley-Tukey FFT for multiplying polynomials. I think I've come up with a pretty nifty algorithm for multiplying polynomials. So my question ...
- 31
3
votes
0
answers
99
views
Checking the generic rank of a matrix
Suppose that $A,B\in M_{p,q}(\mathbb{Z})$ are two rectangular integer matrices of the same size. Suppose that one has a conjecture stating that the rank of the matrix $A+tB$ for Zariski generic values ...
- 16.5k
3
votes
0
answers
107
views
Could a quantum computer factor $N=p\times q$ using Hadamard transforms on $x^2\bmod N$ (instead of Fourier transforms on $a^x\bmod N$)?
In Classically verifiable quantum advantage from a computational Bell test, Kahanamoku-Meyer, Choi, Vazirani, and Yao propose using $x^2 \bmod N$ in an interactive proof-of-quantumness. This is a two-...
- 2,143
3
votes
0
answers
133
views
Recover cyclotomic integer with bounded coefficients from its known associate
Recall that two cyclotomic integers are called associated if their ratio is a unit in the corresponding ring of cyclotomic integers.
We will view cyclotomic integers as polynomials (of degree $<\...
- 30.7k
3
votes
0
answers
130
views
determine degree of boolean polynomial given as black box
I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its ...
- 103
3
votes
0
answers
105
views
Tight bounds on the iterates of the Clenshaw algorithm for Chebyshev polynomials
I'm trying to bound the iterates of the Clenshaw algorithm when applied to the Chebyshev series, related to a question I'm running into related to the stability of this algorithm. Recall that, for $p(...
- 101
3
votes
0
answers
362
views
Conversion of proofs between HoTT and ZFC
HoTT provides a foundation of math that remains mysterious for
many mathematicians including me. Hence this question.
There are several implementations of math based on ZFC, an
example being MetaMath. ...
- 5,038
3
votes
0
answers
178
views
Enumeration of stable graphs of genus $g$
Let $G=(V,E)$ be a connected undirected finite graph, let us call $G$ stable if each vertex has degree at least $3$.
Is there a computer algorithm to efficiently enumerate (repetition allowed) all ...
user39380
3
votes
0
answers
223
views
Max flow with minimum number of edges
A max-flow problem may have multiple solutions. Among these max-flows, I seek the one with the minimum number of positive flow edges (by positive flow edges I mean the edges carrying positive flow). ...
- 436
3
votes
0
answers
105
views
Next smooth number
I want to find the next $n \in \mathbb{N}$ such that
$$s < n = \prod_{p_i \in \mathbb{P}_B} {p_i}^{a_i}$$
Where $\mathbb{P}_B$ is the set of primes not greater than $B$
I know that we can generate ...
- 131
3
votes
0
answers
103
views
Efficient computation of "higher order" Jacobi symbols
Let $N> 1$, and suppose $a \in (\mathbb{Z}/N\mathbb{Z})^{\times}$. There are efficient algorithms to compute the Jacobi symbol $\left(\frac{a}{N}\right)$ using quadratic reciprocity. Fix $k \geq 1$....
- 1,703
3
votes
0
answers
49
views
testing whether a polyhedral complex is convex
Definitions
A (polyhedral) cone in $\Bbb R^n$ is the solution set of a finite number of inequalities of the form $a_1x_1+\cdots+a_nx_n\geq 0$. Note that I don't require strict convexity, i.e. a cone $...
- 3,029
3
votes
0
answers
135
views
Linear combinations of special matrices
I am a hobby computer scientist and I have a problem to which I am searching an efficient algorithm.
Given an integer n, we want to combine some square input-matrices of size n in a way that is ...
- 73
3
votes
0
answers
219
views
Algorithm for regular graphs of tessellation {p,q}
We consider a particular class of tessellations $\{p,q\}$ on a Poincaré disk. There are few examples where a regular graph for a particular tessellation has been obtained. It is done by identifying ...
- 81
3
votes
0
answers
93
views
Random graphs with prescibed degrees and triangles
In short: a random graph model generates (multi-)graphs with prescribed number of edges and minimal number of triangles for each vertex. Questions arise about the actual number of triangles and the ...
- 1,424
3
votes
0
answers
112
views
Applications of products of random matrices
I'm studying the paper "Matrix concentration for products" and I'm trying to find simple applications of the inequalities for the expected value of the spectral norm of products of random ...
- 183
3
votes
0
answers
115
views
Creating an $n\times n$ grid with specified $2\times2$ sums [closed]
Suppose we have an $(n-1) \times (n-1)$ grid $A$ with numbers in each cell.
How can we efficiently create a new $n \times n$ grid $B$ of digits where each $A_{i,j}$ is the sum of the corresponding $2\...
- 31
3
votes
0
answers
88
views
Infection on a complete graph
Suppose we have a complete graph on $2n$ vertices with one "infected" vertex.
At each time step, we form a matching of the vertices. Then the vertices paired with infected vertices will also ...
3
votes
0
answers
189
views
Deterministic Cipolla's algorithm
Cipolla's algorithm for computing square roots in a finite field
(Wikipedia)
requires finding $x$ such that $x^2 - a$ is not a square (for computing a square root of $a$). The usual way to do this is ...
- 31
3
votes
0
answers
157
views
Algorithm to compute minimal polynomials
Suppose $L/K$ is a finite Galois extension of fields of degree $n$. Suppose that we know an irreducible polynomial $f\in K[x]$ such that $L\cong K[x]/(f)$. Suppose also that we know the Galois group ...
- 509
3
votes
2
answers
248
views
Probability that the solution to a combinatorial optimization problem changes after random modifications
Given a combinatorial optimization problem, say the Traveling Salesman Problem, the optimal solution is a set of elements (edges in this case) that satisfy certain constraints (constituting to a ...
- 12.7k
3
votes
0
answers
112
views
Algorithmically computing Weil cohomology groups
Fix a Weil cohomology theory. If I give you a presentation of a smooth projective scheme over an algebraically closed field, do you have an explicit algorithm for computing its cohomology groups? ...
user138661
3
votes
0
answers
72
views
Weighted vertex coloring of hypergraphs
Let $G=(V,E)$ be a simple graph. Let $w$ be a non-negative, integer valued weight function on the vertex set. The chromatic number $\chi(G,w)$ of the vertex-weighted graph $(G,w)$ is defined to be ...
- 151
3
votes
0
answers
72
views
Algorithm to find the minimal number of multiplications
Start with the $\mathbb{Q}$-vector subspace $V_0$ of the polynomial ring $Q[x_1,\ldots,x_n]$ spanned by $\{1,x_1,\ldots,x_n\}$. In each step, we can choose an element of the form $v_iv_i'$ for $v_i,...
- 10.3k
3
votes
0
answers
144
views
Variety Isomorphism Problem for Abelian Surfaces
This is a special case of this question, where it is asked whether there exists an algorithm to determine whether two varieties are isomorphic. There, an answer by Bjorn Poonen explains how to solve ...
- 437
3
votes
0
answers
54
views
Karp hardness of two cycles which lengths differ by one
Our problem is as follows:
NEARLY-EQUAL-CYCLE-PAIR
Input: An undirected graph $G(V,E)$
Output: YES if there exists $2$ (simple) cycles in $G$ which lengths differ by $1$, otherwise NO
Is it $NP$-...
- 121
3
votes
0
answers
129
views
Algorithm detecting all distinct k-th powers in a string for all k ≥ 3
In string theory, the $k$-th power of a string $w$ is named as $w^k$, where $w^0$ is the empty string $\epsilon$ and $w^n$ is the concatenation of $w$ and $w^{n - 1}$ $(n \in \mathbb{N}^{+})$.
The ...
- 123
3
votes
0
answers
604
views
Loopless algorithm for generating permutations (Steinhaus-Johnson-Trotter)
The following is a description of the well-known Steinhaus-Johnson-Trotter algorithm to generate all permutations of an $n$-element ground set using adjacent transpositions.
In fact, it is a loopless ...
- 499
3
votes
0
answers
186
views
Factoring problem similar to $RSA$ structure that is possibly not $NP$ complete and not $coNP$ also?
Standard factoring problem $\Pi_1$ is 'Given integers $N$ and $M$ is there a factor $d\in[1,M]$ of $N$?'. This is in $NP$ since such a factor is the witness and in $coNP$ since one can check all the ...
- 13.7k
3
votes
0
answers
39
views
Constructing a graph with a given number of edges and a given triangle distribution
Give a number of edges $|E|$, number of vertices $|V|$ and a $|V|\times 1$ vector of integers $T=[t_1, \cdots, t_{|V|}]$, I wish to construct an undirected graph with $|V|$ vertices, $|E|$ edges such ...
- 503
3
votes
0
answers
101
views
working with symmetric groups presented via nonstandard generators
This is follow-up to my earlier question.
Suppose that we have elements $\sigma_1,\ldots,\sigma_k\in S_n$, and that we established that these elements actually generate $S_n$.
Since that previous ...
- 16.5k
3
votes
1
answer
90
views
Lattice basis reduction over rings of number fields
Can one use lattice basis reduction algorithms, such as LLL over (low-rank) module lattices over rings of number fields of degree greater than 1? Is there any work on lattice reductions over Euclidean ...
- 1,069
3
votes
0
answers
61
views
Fast Comparing of the Volume of Simplices Defined by Sidelengths
I have a problem, that requires sorting a set of simplices, that are defined via their sidelengths, according to volume; the value of the individual volumes isn't relevant in my problem.
Question:
...
- 12.7k
3
votes
0
answers
128
views
Improving prime number generation probability?
Deterministic generation of primes in polynomial time is unknown.
Is there a way to probablistically in $O(n^c)$ time bound for some $c>0$ generate polynomially $\Omega(n^c)$ many integers in $[0,...
- 13.7k
3
votes
0
answers
111
views
How to compute image of boolean function
I have a function $F: \{0,1\}^n \to \{0,1\}^n$. Denote by $F_i : \{0,1\}^n \to \{0,1\}$ the $i$th component. I assume that for each $i$, $F_i$ can be written as conjunction of at most $n$ ...
- 283