Elementary Definition and 558 Threads

In computational complexity theory, the complexity class ELEMENTARY of elementary recursive functions is the union of the classes










E
L
E
M
E
N
T
A
R
Y





=



k


N



k




-


E
X
P








=


D
T
I
M
E



(

2

n


)




D
T
I
M
E



(

2


2

n




)




D
T
I
M
E



(

2


2


2

n






)









{\displaystyle {\begin{aligned}{\mathsf {ELEMENTARY}}&=\bigcup _{k\in \mathbb {N} }k{\mathsf {{\mbox{-}}EXP}}\\&={\mathsf {DTIME}}\left(2^{n}\right)\cup {\mathsf {DTIME}}\left(2^{2^{n}}\right)\cup {\mathsf {DTIME}}\left(2^{2^{2^{n}}}\right)\cup \cdots \end{aligned}}}
The name was coined by László Kalmár, in the context of recursive functions and undecidability; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY. Most notably, there are primitive recursive problems that are not in ELEMENTARY. We know

LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ RWhereas ELEMENTARY contains bounded applications of exponentiation (for example,



O
(

2


2

n




)


{\displaystyle O(2^{2^{n}})}
), PR allows more general hyper operators (for example, tetration) which are not contained in ELEMENTARY.

View More On Wikipedia.org
  1. S

    Can't solve this elementary school problem involving area of circles

    I can find the area of e and f but otherwise am stuck with many simultaneous equations. i don't think my approach is correct though considering it is an elementary school problem. it should be simpler? 1 semicircle area = π(52)/2 = 12.5π = 39.25 cm2 Square area = 10x10 = 100cm2 Square – 2...
  2. S

    I Only one type of elementary electric charge?

    Is there only one type of elementary charge? The type of elemental charge that appears on particles such as electron, proton, etc. It is well known. Could there be another different type that we don't know yet?
  3. T

    I What makes up the bare mass of elementary particles?

    And as an aside what is the difference between bare mass and invariant mass of such particles?
  4. nomadreid

    Investigating Unexpected Results in Elementary Experiment

    This concerns an elementary experiment that I (a teacher) have done with several secondary school classes, up until now with success. However, I gave the same instructions to a homeschooling student (in another country , so I couldn’t actually directly oversee the experiment), and the...
  5. A

    I Are there any elementary functions of norms that are still norms?

    If ##d(x,y)## is a metric, then it is said ##\frac{d}{1+d}## is also a metric. I don't know the proof of this, I'd appreciate a reference, but it got me wondering: If ##N(x)## is a norm on a Banach space ##x \in X##, then are there functions in a single real (or complex) variable ##f## (besides...
  6. epenguin

    LaTeX Going backwards in elementary Latex

    I am trying to help a student but then I need it myself. Spending all my time writing a simple formula in this hateful Latex which ought to be a thing of the past. Not succeeding in writing the formula, to understand what was going wrong I tried the simplest expressions of the kind for fractions...
  7. Giulio Prisco

    Reversible AND universal elementary cellular automata

    Has any of the reversible extensions of the elementary one-dimensional cellular automata described by Wolfram in NKS (e.g. Rule 37R) been shown to be computationally universal (like Rule 110)? If so, please give me links. Otherwise, could this be the case? Or is there a proof that no nR can be...
  8. V

    B How does exchange of elementary particles result in a force?

    Homework Statement:: I came across the following in an online article. I am unable to understand how these elementary particles cause a force to exist. "Each of the four forces results from the exchange of force-carrier particles.". Above statement is taken from...
  9. B

    InfraRed Detector Mystery (but not Elementary....)

    Hello! I found this circuit element below in a drawer marked "IR detectors" (which I must have written on it myself, a long time ago...although I must admit don't remember doing so #OldAge). First of all, I'm trying to figure out what, exactly, it is. My initial assumption was that it looks...
  10. rstor

    I Keisler Elementary Calculus: computing standard parts of expressions

    In Keisler Elementary Calculus page 39, example 4 it shows how to compute the standard parts of the following expression: Example 4: If ##\epsilon## is infinitesimal but non zero, find the standard part of ##b=\frac {\epsilon} {5-\sqrt{25+ε}}## Before calculating the standard parts the...
  11. A

    I Plasma-like Description for Elementary and Composite Quantum Particles

    My article has been published in Entropy . Abstract: Schrödinger noticed in 1952 that a scalar complex wave function can be made real by a gauge transformation. The author showed recently that one real function is also enough to describe matter in the Dirac equation in an arbitrary...
  12. D

    I Elementary Functions - What Is The Exact Definition?

    Mathematicians will use the term "elementary functions," often in the context of integration wherein some integrals cannot be expressed in elementary functions. The elementary functions are usually listed as being arithmetic, rational, polynomial, exponential, logarithmic, trigonometric...
  13. B

    I Elementary Ideas About Entropy -- Is this textbook example correct?

    Summary:: An elementary example calculation involving entropy in a textbook seems wrong I was reading an elementary introduction to entropy and the second law of thermodynamics. The book gave the example of a gas in a chamber suddenly allowed to expand into an additional portion of the...
  14. C

    I Factoring Matrices with Elementary Row Operations

    Dear Everybody, I have some trouble with this problem: Finding a sequence of elementary matrix for this matrix A. Let ##A=\begin{bmatrix} 4 & -1 \\ 3& -1\end{bmatrix}##. I first used the ##\frac{1}{4}R1##-> ##R1##. So the ##E_1=\begin{bmatrix} \frac{1}{4} & 0 \\ 0& 1\end{bmatrix}##. So the...
  15. vanhees71

    I Manuscript on elementary rigid-body dynamics

    In view of questions occurring from time to time in this forum, I've written an elementary introduction to rigid-body dynamics (mostly about the force-free and the heavy symmetric top). I hope, it's of some use: https://itp.uni-frankfurt.de/~hees/pf-faq/spinning-top.pdf
  16. F

    MHB Find the elementary divisors and invariant factors

    Hello I have problems with this exercise Find the elementary divisors and invariant factors of each of the following groups a) $G1= Z_6 \times Z_{12} \times Z_{18}$ , b) $G_2= Z_{10} \times Z_{20} \times Z_{30} \times Z_{40}$Thanks
  17. daisey

    I Down Quark: Composed of Up Quark and Electron?

    I have no formal Physics training, just what I've read over time. And I've always read and understood that Quarks are Elementary Particles. I was reading on the web today where someone who seemed to know what he was talking about stated that Down Quarks are not really elementary particles, but...
  18. JD_PM

    High Energy Books on the Standard Model of elementary particle physics & beyond

    Hello! I am taking a course on Electroweak & Strong Interactions (you could equally call it Standard Model I) and I find it absolutely fascinating! 😍 We studied how weak interactions violate parity, introduction to QCD, flavor physics (CKM matrix, CP violation, …) and neutrino physics...
  19. Frabjous

    Engineering Advanced Approach to Elementary Engineering Statics and Dynamics

    I already have a degree in physics. Is there a book that describes the applications for a person who knows the underlying physics? Poking around, I can only found 1000 page tomes that are also teaching the underlying physics. In the back of my head I am thinking about 1) Systems of wheels...
  20. G

    I Skipping elementary calculus and starting at analysis?

    I was walking around with my head in the clouds and suddenly I wondered if a smart person, say, a philosopher, could start at the full monster of real analysis instead of elementary calculus. Would there be any hope for this unfortunate soul? What are your opinions and why? Or if you feel this...
  21. A

    A Is the notion of elementary function a fluid concept among algebras?

    Let's consider the Taylor power series of a function on real numbers. Some of them represent elementary functions, and some of them represent special functions. The special functions cannot be expressed via finite combination of elementary functions on real or complex numbers. Now, take some...
  22. epenguin

    Elementary question about WolframAlpha

    I am trying to use this WolframAlpha app (free if I remember) to portray some 3D surfaces. Having succeeded up to a point I don't want to switch to anything else while I complete an investigation bearing on some homework help. Although I have read stuff claiming Wolfram is a smart system that...
  23. chwala

    Elementary algebra: find the value of x

    ##\frac {7}{2x+2}=\frac {4x-3}{-2x-2}## ##-7(2x+2)=(4x-3)(2x+2)## ##x^2+2x+1=0## ##x=1## or ##x=-1## can we also have; ##-7=4x-3## can the ##2x+2## cancel out? i am a bit mixed up on this very simple problem...and why am i getting false on my ti nsipre...
  24. nomadreid

    I Does intrinsic (e.g., spin) imply elementary (irreducible)?

    Some time ago, before particles turned out to be mutable wave excitations (making Alchemist's dreams sound nicer, I guess :-) ) , to say that something was an "elementary particle" meant that it couldn't be broken down further. OK, that idea bit the dust, but now there are intrinsic...
  25. U

    Other Which Introductory Linear Algebra Book Is Best for Aspiring Engineers?

    Hello I am looking for an introductory linear algebra book. I attend university next year so I want to prepare and I want to become an engineer. I have a good background in the prerequisites, except I don't know anything about matrices or determinants. I am looking for the more application side...
  26. J

    A Griffith's Elementary Particles Section 9.7 Electroweak Unification

    1. On pg. 343 Griffith's expresses the weak current in terms of left-handed doublets. jμ± = ##\bar χ_L##γμτ±##χ_L## ##χ_L## = ##\begin{pmatrix} ν_e \\ e \end{pmatrix}_L## ##\tau^+## = ##\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}## , ## \tau^- ## = ##\begin{pmatrix} 0 & 0 \\ 1 & 0...
  27. W

    Python Elementary Python Questions: Data Frames, k-nary functions

    Hi All, A couple of questions, please: 1) Say df is a dataframe in Python Pandas, and I select a specific column from df: Y=df[column].values. What kind of data structure is Y? 2) I want to find the sum of two numbers: Def Sum(a=0,b=0): return a+b If I want to find a sum over sum data...
  28. hagopbul

    Intro Physics Finding Books on Elementary Particle Physics & Special Relativity

    hello all : looking for books to read in this times ,undergraduate level mostly , but i have some problem finding good ones for introductory elementary particle physics other than griffths and for special relativity any recommendations
  29. M

    MHB Topic of presentation: Elementary Geometry vs Fibonacci & its sequences

    Hey! 😊 Between the following two topics: Elementary Geometry Fibonacci and its sequences which would you suggest for a presentation? Could you give me also some ideas what could we the structure of each topic? :unsure:
  30. J

    B String Theory & Elementary Particles: What's Real?

    If string theory is correct does it mean that elementary particles like photons, electrons, and quarks don't really exist or does it mean they do but are made of cosmic strings and so therefore are not elementary?
  31. J

    I Group Theory Appearing in Griffith's Elementary Particles (2nd Ed.)

    Hello, I'm trying to make sense of some of the group theoretic discussion found in Griffith's Introduction to Elementary Particles. I have had a fair amount of exposure to elementary group theory, but no representation theory, and have some specific questions related to this which refer to the...
  32. LittleRookie

    B Before understanding theorems in elementary Euclidean plane geometry

    Before looking at the proof of basic theorems in Euclidean plane geometry, I feel that I should draw pictures or use other physical objects to have some idea why the theorem must be true. After all, I should not just plainly play the "game of logic". And, it is from such observations in real...
  33. LittleRookie

    B Elementary analytic geometry textbook recommendation

    Every explanation about scaling a 2D vector, or equivalently having a line segment PQ on cartesian plane and then find a point R on the line PQ satisfying PR/PQ = r (fixed given r) starts with that one specific case in the picture. A formula for the coordinates of R is then given for that case...
  34. S

    I An elementary question about rotations

    Suppose I have a positive spin-##1/2## eigenstate pointing in the ##z##-direction. If I apply a rotation operator by an angle ##\theta## around the ##z##-axis the state should of course not change. However, if I write it out explicitly, I find something different: $$R_z(\theta)|\uparrow\rangle =...
  35. nmsurobert

    B Can elementary particles truly be at rest in an E field?

    I'm working on E fields and particles in E fields, and I was wondering if particles are ever truly accelerated from rest. I did some reading on how accelerators work and cathode tubes, but it seems that particles are always in some type of motion. Is this just a thing for introductory level...
  36. kmm

    Particle Is Griffiths Introduction to Elementary Particles up to date?

    I have a copy of Griffiths Introduction to Elementary Particles (1st Edition) and was thinking of beginning to work through it. I was curious if anyone knows if this text is sufficiently up to date or if there have been any major developments in particle physics that would make it worth getting...
  37. matqkks

    I Why certain topics in elementary number theory?

    Why do all elementary number theory courses have the following topics - gcd, linear Diophantine equations, Fundamental Theorem of Arithmetic, factorization, modular arithmetic, Fermat's Little Theorem, Euler's Theorem, primitive roots, quadratic residues and nonlinear Diophantine equations?
  38. matqkks

    MHB Why certain topics in elementary number theory?

    Why do all elementary number theory courses have the following topics - gcd, linear Diophantine equations, Fundamental Theorem of Arithmetic, factorization, modular arithmetic, Fermat's Little Theorem, Euler's Theorem, primitive roots, quadratic residues and nonlinear Diophantine equations?
  39. F

    A 3D Heat equation with elementary Dirichlet BC

    Hi, I am looking for the solution of the following heat conduction problem (see figure below): the geometry is the semi-infinite domain such that (x,y)∈R2 and z∈[0,∞[ ; the thermal diffusivity is constant; the domain is initially at a temperature of 0; At t>0, a small square of the surface...
  40. SSequence

    I An Elementary Observation Regarding Definability

    Few months ago there was a discussion in the topic(Complex numbers in QM) regarding the notion of definable real numbers. The discussion was in the first 3 or 4 pages of that topic. Anyway, I thought of a reasonably interesting observation about it. Since the main theme of that topic seems...
  41. M

    Elementary question on car crashes and momentum

    When two cars crash into one another they generally come to a stop, yet we are told momentum cannot be created or destroyed. Where did their momentum go? It seems like the kinetic energy went into the damage in the vehicles but apparently that has nothing to do with momentum?. Thanks...
  42. F

    A Why do we know that an elementary particle is a point particle?

    Elementary particle can be consider as a "wave packet" of the field,but a "packet" of field must have a size.Why do we know elementary particle is point particle?
  43. A

    What could elementary school teachers do to better prepare students?

    Physics forums members have ranted how high-school did not prepare students for college. However, I think that elementary school is as equally as important as high-school. Members have should be ranting about elementary school teachers too. The willingness to do homework is a skill that students...
  44. matqkks

    I What should I say about elementary number theory?

    I need to give an option talk about elementary number theory module. I will discuss how it is study of positive integers particularly the primes and give some cryptography applications. What is a good hook to stipulate in this talk regarding an introduction to elementary number theory?
  45. matqkks

    MHB What should I say about elementary number theory?

    I need to give an option talk about elementary number theory module. I will discuss how it is study of positive integers particularly the primes and give some cryptography applications. What is a good hook to stipulate in this talk regarding an introduction to elementary number theory?
  46. C

    MHB Elementary Number Theory proof

    Dear Everyone, Here is the question: "Prove that if $k$ divides the integers $a$ and $b$, then $k$ divides $as+bt$ for every pair of integers $s$ and $t$ for every pair of integers." The attempted work: Suppose $k$ divides $a$ and $k$ divides $b$, where $a,b\in\mathbb{Z}$. Then, $a=kt$ and...
  47. R

    I Are some elementary particles too massive to obey QM?

    I understand photons and elections fit into the probalistic rules of QM. Are there any other elementary particles (more massive) that don’t obey the point/wave duality?
  48. Cantor080

    Artistic sense-ualisation of elementary origins of the Universe

    I am searching sources, which would express purely (without any other expression on how the data was obtained, etc.) elementary origins of the universe. As we would have certain artistic visualisation on how our Mars rover would operate on landing on mars, are there sources which give data on...
Back
Top