Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with algorithms
Search options answers only
not deleted
user 3106
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.
6
votes
Formal verification in complexity theory
The same comment and question could be applied to just about any area of mathematics. To my knowledge, nobody has really worked on formalizing computational complexity theory. Formalization is still …
- 82.6k
5
votes
Accepted
Checking whether a set family forms a matroid.
One way is to delete an element $x$ from your alleged matroid $M$, recursively check that the smaller structure $M'$ is a matroid, and then check that adding back $x$ gives you a single-element extens …
- 82.6k
4
votes
Is this problem on weighted bipartite graph solvable in polynomial time or it is NP-Complete
The problem is NP-hard. Without loss of generality we shall prove this in the case that all the weights are positive integers. First let us rephrase the problem as follows.
Given an integer-valu …
- 82.6k
9
votes
Accepted
Fastest algorithm to compute the width of a poset
See "Recognition algorithms for orders of small width and graphs of small Dilworth number," by Felsner, Raghavan, and Spinrad, Order 20 (2003), no. 4, 351–364. …
- 82.6k
15
votes
Definition of relativization of complexity class
[EDIT: I wrote my original answer when I was in a bit of a hurry. I have now expanded my answer.]
The short answer is no. The simplest way to see that $C^A$ cannot possibly depend only on $C$ and $ …
- 82.6k
1
vote
Computational cost of extracting a proof
This is a suggested clarification of the question; judging from the responses, I think the question is not completely clear. [EDIT: Under the assumption that this clarification is correct, an answer …
0
votes
Algorithmic Combinatorics resources?
I have often turned to Combinatorial Algorithms: Generation, Enumeration, and Search by Donald L. Kreher and Douglas R. Stinson when I have needed to implement a basic combinatorial algorithm. …
4
votes
Books/Lecture notes which contrast Risch algorithm with basic standard procedure of finding ...
It is the most complete implementation of symbolic integration algorithms to date.
The book is a very nice blend of practical algorithms and general theory. …
- 82.6k
3
votes
Reachability in digraphs
Another paper on this topic that you may find useful is Mikkel Thorup's Compact oracles for reachability and approximate distances in planar digraphs, J. ACM 51 (2004), no. 6, 993-1024. The abstr …
- 82.6k
2
votes
Accepted
Looking for J.-C. Deville technical report from 2000
I wrote to Yves Tillé and he sent me a scan of a handwritten draft of the report. It seems likely that this is the best one can hope for.
11
votes
Some Questions on the Collatz conjecture (reexpressed as "equivalence relation")
This problem is still open. See for example Sections 2.6 and 2.7 of Lagarias's survey.
- 82.6k
10
votes
Accepted
Suppose the independent number of a graph is bounded. How small the clique number can be?
So for example Kim (Random Structures and Algorithms 7 (1995), 173-207) showed that $R(3,t)\asymp t^2/\log t$. …
- 82.6k
5
votes
Alternate algorithms for Chinese remainder theorem
If you're using the (extended) Euclidean algorithm to compute modular inverses mod $m$, then the time complexity is roughly $O((\log m)^2)$. So if $m = abc$ then you'd prefer to do $(\log a)^2 + (\lo …
- 82.6k
11
votes
Accepted
Graph minor check
Kezdy, "Sequential and parallel algorithms to find $K_5$ minor," SODA 1992, pp. 206–215. …
- 82.6k
1
vote
Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?
For random graphs, there are algorithms that are efficient on average. … You can use Google Scholar to find papers that cite this one; that should point you to some good solving algorithms. (EDIT: I see now that FHCP was mentioned in another answer.) …
- 82.6k